Archive for the "Math" Category

《编程之美》趣味算法——控制CPU占用率曲线

问题:

用程序控制Windows任务管理器中的CPU占用率,包括以下三种情况:

1、固定在50%

2、固定在某一个值,这个值由用户决定

3、曲线是一条正弦曲线

分析:

首先来观察一下任务管理器,可以得到以下结论:

  • 大约1秒钟更新一次CPU占用率
  • 系统空闲的情况下,CPU占用率在5%以下,但是只要有轻微动作,包括鼠标移动,就会影响占用率
  • CPU空闲时,一个叫System Idle Process的进程占用了CPU

在任务管理器的一个刷新周期内,CPU忙和空闲时间的比值就是占用率。这样,可以写一个程序,控制CPU忙的时间即可。而让CPU忙可以用循环解决(想想死循环时CPU就100%的情况),而空闲可以用Sleep解决

解法:

1、让CPU在周期内运行busy和idle两个循环,通过控制比例来控制占用率。这里关键是估算50%所需的循环量。这里要注意一个问题,在一秒钟的周期里,不能够一次性运行完循环,然后彻底休息。这样很容易造成锯齿状的忽高忽低现象。以下是问题一的Code:

2、解法一的问题在于估算的难度和不准确。解法二使用GetTickCount函数获取运行时间,然后让循环和空闲运行相等的时间即可。

3、解法二中的做法可以精确调整循环和空闲的比例,因此调整比例就可以做出正弦曲线。

4、解法三在单核CPU上运行良好,在多核CPU上可以使用GetCurrentProcessSetProcessAffinityMask函数控制进程在制定CPU上运行。

以下是四个解法的Code:

// 解法1
int main()
{
for(;;)
    {
for(int i = 0; i < 9600000; i++)
            ;
        Sleep(10);
    }
return 0;
}
// 解法2
int main()
{
int busyTime = 10;  // 10ms
int idleTime = busyTime;  // 50% Usage
long startTime = 0;
while(1)
    {
        startTime = GetTickCount();
while1;
        idleSpan[i] = INTERVAL – busySpan[i];
        radian += SPLIT;
    }
    DWORD startTime = 0;
int j = 0;
while(1)
    {
        j = j % COUNT;
        startTime = GetTickCount();
while2;
24         idleSpan[i] = INTERVAL – busySpan[i];
25         radian += SPLIT;
26     }
27     DWORD startTime = 0;
28 int j = 0;
29 while (true)
30     {
31         j = j % COUNT;
32         startTime = GetTickCount();
33 while ((GetTickCount() – startTime) <= busySpan[j]) ;
34         Sleep(idleSpan[j]);
35         j++;
36     }
37 return 0;
38 }

呵呵,没事的时候钻研一下貌似感觉不错!

  1. GetTickCount() – startTime) <= busyTime)
                ;
            Sleep(idleTime);
        }
    }
    // 解法3
    #include <windows.h>
    #include <stdlib.h>
    #include <math.h>
    const double SPLIT = 0.01;
    const int COUNT = 200;
    const double PI = 3.14159265;
    const int INTERVAL = 300;
    int main()
    {
        DWORD busySpan[COUNT];
        DWORD idleSpan[COUNT];
    int half = INTERVAL / 2;
    double radian = 0.0;
    for(int i = 0; i < COUNT; i++)
        {
            busySpan[i] = (DWORD)(half + (sin(PI * radian) * half []
  2. GetTickCount() – startTime) <= busySpan[j])
                ;
            Sleep(idleSpan[j]);
            j++;
        }
    return 0;
    }

    解法四

    1 #include “Windows.h”
    2 #include “stdlib.h”
    3 #include “math.h”
    4
    5 const double SPLIT = 0.01;
    6 const int COUNT = 200;
    7 const double PI = 3.14159265;
    8 const int INTERVAL = 300;
    9
    10 int _tmain(int argc, _TCHAR* argv[])
    11 {
    12 SetProcessAffinityMask(
    13 GetCurrentProcess(),
    14 0×00000001          //cpu mask
    15         );
    16
    17     DWORD busySpan[COUNT];  //array of busy times
    18     DWORD idleSpan[COUNT];  //array of idle times
    19 int half = INTERVAL / 2;
    20 double radian = 0.0;
    21 for(int i = 0; i < COUNT; i++)
    22     {
    23         busySpan[i] = (DWORD)(half + (sin(PI * radian) * half []

May 22nd, 2008

在一个平面上画1999条直线,最多能将这一平面划分成多少个部分?

看到这个题目,转载一下:

 

平面上只要多出现一条直线,就能至少多把平面分出一部分,而若此直线与其他直线有n个交点,就再能把平面多分出n个部分,因此若想把平面划分的部分最多,新添入的直线必须与前k条直线交k个点,即第二条直线要与第一条直线交1个点,第三条要与前两条交2个点,……,第1999条与前1998条交1998个点,这样,第二条直线多划分出1+1=2个部分,第三条直线多划分出1+2=3个部分,……,第1999条直线多划分出1+1998=1999个部分。而第一条直线把平面划分出2个部分,因此1999条直线能划分平面的块数为:
2+2+3+4+5+…+1998+1999
=1+(1+2+3+4+5+…+1998+1999)
=1+(1+1999)*1999/2
=1999001

May 21st, 2008

我的数学书

数学书目录:

图的嵌入式理论

九章算术导读与译注

复变函数逼近论

抽象代数学卷2:线性代数

抽象代数学卷3:域论与加罗瓦理论

概率论与数理统计学习指导

概率论与数理统计

概率论基础和随机过程

线性算子普空间2——不定度规空间

无穷维随机分析引论

涡度法

线性模型参数的估计理论

统计渐进论基础

自然边界原方法的数学理论

November 13th, 2007

阿基米德的报复——保罗•霍夫曼 著  尘土等译

阿基米德的报复

本书主要概述了数学所涉及的领域和范畴。我并不认为这本书包罗万象,然而它选择的主题很离奇,但它也只能如此。数学是世间每所大学都从事研究的一门学科,它至少像生物学一样有广泛的领域,在生物界中,某个研究人员正努力研究艾滋病毒,而另一个研究人员则在研究袋熊的社会化问题。……第一篇 数 字  第一章 邪恶的数和友好的数   毕达哥拉斯及其好友认为,整数的完满性,即完全数是任何其所有除数之和(该除数本身外)等于该数本身的整数。第一个完全数是6。它可被123整除并且是123之和。第二个完全数是28。它的除数是124714,这些数加起来为28。希腊人所知道的就是这些,尽管他们做过尝试,但没有发现奇数完全数。……  第二章 阿基米德的报复   按照阿基米德的愿望,人们在他的墓碑上刻了一个圆柱体,柱体里面是一个球体——象征着他的骄傲的发现:球的体积是装下该球的最小的圆柱体体积的三分之二。……  第三章 素数的滥用  然而在今天,这座宫殿里却出了问题。那最纯的论题——素数正在以国家安全的名义滥用自己。据报道我们政府所用的某些最好的密码是依靠素数创制的。在这些密码中,字母被转换成数字,其根据纯然是数学的:某些计算程序较易创制但极难破译。例如,计算机计算两个100位数的素数的积极其容易。但已知那个200位数的积去恢复那些素数除数却极其困难(当然,除非有人告诉你)。 ……  第四章 比尔密码之谜

  密码学——编制和破译密码的科学——日益成为那些能够获得最新计算机技术的数学家所从事的量性学科。今天在军队和私人企业中所使用的密码与昨日的密码截然不同,总的来说是变得更为难以破译了。然而,尽管取得了这些进步,这种新型的数学密码在许多场合也不管用,而对一些古老的密码,最先进的破译技术仍然无法解开。……

请使用下载软件下载

PDF下载

November 13th, 2007

一个数学家的辨白——[英]G·H·哈代

一个数学家的辨白

[英]G·H·哈代

From 北大未名站 信区: Mathematics

假如真的能把我的雕像塑在伦敦纪念碑上的话,我是希望这座碑高耸入云,以至人们见不到雕像呢,还是希望纪念碑矮得可以使人们对雕像一目了然呢?我会选择前一种,而斯诺博士可能会选择后一种。

序 言

 我感谢C·D·布劳德(Broad)教授和C·P·斯诺博士对我提出的许多宝贵的批评。他们读过我的初稿。我已将他们提出的所有建议的内容实质差不多都写入了我的书中,同时删除了许多生硬晦涩的词语。

但是有一种情况我是以不同的方式处理的,那就是§28。这一章节是在我的一篇短文的基础上撰写的。那篇短论文是在年初我投稿到《我发现了》(此杂志是由剑桥阿基米德协会主办的学术刊物)的。对这篇不久前我曾以非常认真的态度写出的东西加以修改,我的确感到为难。再说,假如真要我设法接受这些批评(即严肃地看待这些重要的评论),那我就只得将这章节大大扩展,直至完全破坏这篇论文,使其面目全非。鉴于此,我就没改动它,而是把批评家对我论文所作的评论的要点之简述以脚注的形式加在文章最后。

G·H·哈代

1940年7月l8日

请使用下载软件下载

PDF下载

November 13th, 2007

100个著名初等数学问题

100个著名初等数学问题

第01阿基米德分牛问题Archimedes’ Problema Bovinum
太阳神有一牛群,由白、黑、花、棕四种颜色的公、母牛组成.
在公牛中,白牛数多于棕牛数,多出之数相当于黑牛数的1/2+1/3;黑牛数多于棕牛数,多出之数相当于花牛数的1/4+1/5;花牛数多于棕牛数,多出之数相当于白牛数的1/6+1/7.
在母牛中,白牛数是全体黑牛数的1/3+1/4;黑牛数是全体花牛数1/4+1/5;花牛数是全体棕牛数的1/5+1/6;棕牛数是全体白牛数的1/6+1/7.
问这牛群是怎样组成的?
第02德·梅齐里亚克的法码问题The Weight Problem of Bachet de Meziriac 
一位商人有一个40磅的砝码,由于跌落在地而碎成4块.后来,称得每块碎片的重量都是整磅数,而且可以用这4块来称从1至40磅之间的任意整数磅的重物.
问这4块砝码碎片各重多少?
第03牛顿的草地与母牛问题Newton’s Problem of the Fields and Cows
a头母牛将b块地上的牧草在c天内吃完了;
a’头母牛将b’块地上的牧草在c’天内吃完了;
a”头母牛将b”块地上的牧草在c”天内吃完了;
求出从a到c”9个数量之间的关系?
第04贝韦克的七个7的问题Berwick’s Problem of the Seven Sevens
在下面除法例题中,被除数被除数除尽:
* * 7 * * * * * * * ÷ * * * * 7 * = * * 7 * *
* * * * * *
* * * * * 7 *
* * * * * * *
* 7 * * * *
* 7 * * * *
* * * * * * *
* * * * 7 * *
* * * * * *
* * * * * *
用星号(*)标出的那些数位上的数字偶然被擦掉了,那些不见了的是些什么数字呢?

请使用软件下载

PDF下载

November 13th, 2007

解读求pi的怪异代码

/*某年Obfuscated C Contest佳作选录:*/
#include < stdio.h>
long a=10000, b, c=2800, d, e, f[2801], g;
main(){
for(;b-c;)f[b++]=a/5;
for(;d=0,g=c*2;c-=14,printf(“%.4d”,e+d/a),e=d%a)
for(b=c;d+=f[b]*a,f[b]=d%–g,d/=g–,–b;d*=b);
}

/* (本程式可算出pi值连小数点前共800位)
(本程式录自sci.math FAQ,原作者未详)*/

这段代码可以用来求解pi的前800位,原文地址 这里有详细的解析

October 10th, 2007

数学家和数学

一本介绍数学家和数学史的书

Heroes In My Heart.pdf(本地)

Heroes In My Heart.pdf(下载)

October 9th, 2007

Hash函数学习

Hash函数是一种映射关系,通过一种映射关系,将原本的字符串,数字或其他关键信息转换为一个索引值。
用数学关系式表示为:
   index  =  function(key)

数序上有不同的映射关系,不同的key,有可能会获取相同的index,这个时候的index就是有重码,也就是collosion,这就导致了Hash函数的不唯一性,从而在查找index下的关键字时也是有冲突的。

目前一些常用的数学映射关系为:
   1、直接定址法,就是直接使用key作为index
   2、数字分析法,取key中的若干位数作为index,有较多冲突
   3、平法取中法,取key的平方,然后取中间几位作为index(index与key值密切相关),
   4、折叠法,将key从中间分割成几个部分,然后按照一定规则相加获取的结果为index。
   5、除留余数法,将key对某个数值m求余,获取的余数即为index,显然indxe<m,也就是如果key>m,必然会有n-m个冲突存在(n为key关键字的个数)。
   6、随机数法,将key值通过随机数求取index,即function(key)=random(key),伪随机数的均匀性较好,当关键字长度不相等时,用此法构造较为恰当。

解决冲突:
    其实并不是将冲突去掉,而是通过一种变通的方法,将冲突变得可以唯一查找,而不是有冲突就没有唯一的index位置了。
   解决方法有:
    一、开放定址法:
             index = (function(key)+di)mod m
               di:增长序列,m哈希表长,d的求取方法有下面集中。
      1、线性探测再散列,就是查找或插入时,如果发生冲突,就线性排列下去,下面还有冲突,继续排列下去,直到没有冲突时,查找结束或添加index。d=1,2,3,……,m-1
     2、二次探测再散列,d=1^2,-1^2,2^2,-2^2,……,±k^2(k<=m/2)
     3、伪随机探测再散列,d=random(key)
  二、再Hash法
        即将index冲突的key关键字进行另一种Hash算法,得到key关键的index2索引值,从而来降低和避免冲突,当然要将冲突完全避免,则需要多个Hash算法隐含在其中。
 三、链地址法
        当Index发生冲突时,将同一个index下冲突的key值都放在以index开头的链表中,这样index开头的链表中的key都可以比较方便的查找出来。
四、建立溢出表
         建立一个和key关键字一样多的index索引,当index发生冲突时,将所有发生冲突的key或index都放在溢出表中。

Hash表查找:
  

// ——-开放定址Hash表的存储结构————
int hashsize[]={997,…};  //Hash表容量递增表,一个合适的素数序列
typedef struct{
   ElemType 
*elem;           //数据元素存储基址,动态分配数组
   int              count;          // 当前数据元素的个数
   int              sizeIndex;   //hashsize[sizeIndex]为当前容量
}
HashTable;

//——–链接地址Hash表的存储结构—————
typedef struct childchain
{
   ElemType data;   // 数据值
   struct childchain *next;  // 下一个childchain值,NULL结束
}ChildChainHash

  typedef struct mainchain{
    int index;   // 主链的索引值
    ChildChainHash  *child;  // 指向冲突的child子链,当没有冲突时,给予NULL值。
   struct mainchain *main;  //
}MainChainHash;

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

采用链接构建Hash的思路,MainChainHash申请一个head指针和若干个变量,然后main指针依次指向下一个MainChainHash指针,而每一个child指针,指向ChildChainHash链中的值,这样一个Hash表就 构造完成了。当主键key使用Hash一下获取的Index时,通过Index索引值知道Child链,从而构造了一个核实的Hash表。

// 采用开放式哈希表的存储结构

Status SearchHash(HashTable H, KeyType k, 
int &p, int &c)
{
     
// 开放地址哈希表H中查找关键字k的元素,若查找成功,以p指示待查数据,
   
// 元素在表中位置,并返回SUCESS,否则,以p指示插入位置,并返回UNSUCESS,
   
// c用以计冲突次数,其初值置零,供建表插入时参考
  p  = Hash(k);   // 求得hash地址表
  while( H.elem[p].key != NULLKEY &&   //该位置中填有记录
           !EQ( k,H.elem[p].key)                 // 并且关键字不相等
          collision( p, ++c) ;                  // 求得下一探索地址p
   if (EQ(K, H.elem[p].key ) )
          
return SUCCESS;                 // 查找成功,p返回待查数据元素位置
   else
         
return UNSUCESS;              // 查找不成功.( H.elem[p].key == NULLKEY )
                                                      
// p返回的是插入的位置
}
// SearchHash

Status InsertHash( HashTable 
&H, ElemType e)
{
     
// 查找不成功时,插入数据元素e到开放定址Hash表H中,并返回OK,
    
// 若冲突次数过大,需重新构建Hash表
   c = 0;
   
if( SearchHash( H,e.key,p,c ))
        
return DUPLICATE;           // 表中已有与e有相同关键字的元素
  else if ( c <hashsize[H.sizeindex]/2 )  //冲突次数c未达到上限时,(c的阈值可调)
  {
         H.elem[p] 
= e; ++H.count; return OK;    // 插入e
   }

   
else 
  
{
     RecreateHashTable(H);
    
return UNSUCESS;    // 重建hash表
  }

}
  // InsertHash
摘抄自严蔚敏的C数据结构中Hash章节。

Hash表最大的特点:
    不管n有多大,即表有多长,我们总可以选择一个合适的装填因子以便将来平均查找长度限定在一个范围之内。

查找长度
链地址:
          S=1+α /2
线性探测:
          S = 1/2 (1+1/(1-α ) )
伪随机探测:
          S = -1/
α ln(1-α )

October 8th, 2007

Space_time trade-offs in hash coding with allowable errors.pdf

This pdf:  pdf

October 8th, 2007
本WordPress博客由爱写字提供技术支持