首页 > 代码库 > 【程序员的数学思维修炼】总结一

【程序员的数学思维修炼】总结一

2024-07-07 21:42:17   228人阅读

第一章 数据的表示
主要学习了会了
  1. 0 不是什么都没有，比如在java里BigDecimal里面是根据最高的那个精度来的，比如1.99+0.01=2.00 这时候提交可能会判错，所以要去掉后导零
  2. 为啥要用二进制
  3. 还有哪些进制，神奇的八卦，八进制、钟表使用的十二进制、半斤八两十六进制、60年一个甲子六十进制

关于二进制，最主要的是要熟练掌握位运算！一些做题中常用的技巧，比如求n的m次方，判断奇偶，统计一的个数，

这一章里还提到了20！阶乘问题，还记得怎么解决大数阶乘吗。

第二章 神奇的素数
1.验证素数的算法，最容易想到的就是 确定性算法--试除法
for(int i=2;i<=sqrt(n);i++){
     if(n%i==0){
        return false; 
    }
        return true;
}
2.再就是，寻找素数的算法，著名的埃拉托斯特尼筛法 Eratosthenes求素数
假设有一个筛子，用来存放2~100之间所有的数，由于偶数都能被2整除，因此所有的偶数都不是素数（2除外）
接着再将3的倍数筛去，5的倍数筛去……
for(int i=2;i<=maxnum;i++){
      prime[i]=1;        //初始化数组，标志为1表示对应的数是素数
}
for(int i=2;i*i<maxnum;i++){
     if(prime[i]==1){
         for(j=2*i;j<=maxnum;j++){
               if(!prime[j])continue;
               if(j%i==0)prime[j]=0;
         }
     }
}
//输出素数
for(int i=2;i<maxnum;i++){
      if(prime[i]==1){
      printf("%4d ",i);
      c++;
      if(c%10==0){
      printf("\n");
      }
      }
}
做题当中很重要的一个想法就是，有一个标志数组，来标记当前的状态。像DFS中是否被访问过，并查集中表示位移偏量，是否是素数，以及当前节点可不可达……

3.孪生素数
什么是孪生素数。是指间隔为2的相邻素数，他们之间的距离已经近的不能再近了，就像孪生兄弟一样，因此叫做孪生素数，又叫做双生素数。
//下面统计孪生素数
int twin=2;
for(int i=2;i<maxnum;i++){
     if(prime[i]==1){
          c++;//素数的个数
      if(i-2==twin){
         printf("(%d,%d)",twin,i);
         t++;//孪生素数的对数
      }
      twin=i;
     }
}
孪生素数的公式，
对于自然数Q和Q+2，若都不能被小于sqrt(Q+2)的任何素数整除，则Q与Q+2就构成一对孪生素数。这句话可以用下面的公式来表达：
Q=P1M1+B1
 =P2M2+B2
 =P3M3+B3
  ......
 =PkMk+Bk
p1,p2,p3..表示从小到大的素数2,3,5，...Bi≠0且≠Pi-2
如Q=29，可分解为以下算式：
   29=2 *14 +1（2M+1）
     =3 * 9+2  (3M+2)
     =5 * 5+4  (5M+4)

下面没看懂，看懂了再说吧。
4.反正是由此引出了中国剩余定理
韩信点名的故事，…汉军原有士兵1500人…他命令士兵3人站成一排，结果多出两名，接着命令士兵5人站成一排，结果多出三名，又命令7人站成一排，结果多出两名。韩信马上乡将士们宣布，我军有1073名士兵……

对于这个问题，可以将其描述为一个数学问题，就是一个数除以3余2，除以5余3，除以7余2，求这个数是多少？
（很多时候把一个生活中的问题，去掉不相干的因素抽象出一个数学问题是很重要的，要从平时多练，我们从小学就开始做应用题，结果长大了反而不会了。不要等着别人给你打上标签说这是个数学问题，你才会想要转成数学问题，关键是要培养一种思考问题的方式，一种思维）

设这个数为X，则
X%3=T1...2
X%5=T2...3
X%7=T3...2
直观的想法是，把符合上面三个算式的所有数字都列出来，找第一个共同出现的数字。
先列出除以3余2的数
          2, 5, 8, 11, 14, 17, 10.......
再列出除以5余3的数
          3， 8， 13， 18， 23， 28......
在这两列数当中，首先出现的公共数是8,3与5的最小公倍数是15，两个条件合并成一个就是：
          8+15*n
将n分别取1、2、3……即可得到数列
          8, 23，38……
再列出除以7余2的数：
          2，9, 16, 23, 30……
可以看出最小符合条件的数字是23
也就是说，我们已经可以把题目当中三个条件合并成一个：该数除以105余23.
由于汉军原有士兵1500人，死伤四五百人，即剩余的士兵应该为1000余人，即可得到士兵的总数:
105*10+23=1073人

※要学会把三个规模的问题转变成两个规模的问题，推而广之，要学会把一个n规模的问题转变成n-1规模的问题，进而转变成2个规模的，1个规模的，0个规模的，比如约瑟夫环问题，背包问题，以及那个脑筋急转弯头上画蓝色的标记问题……

那将这个问题推而广之到一个一般性的解法：
 所求的数字S 应满足S= T1 * K1 + N1
                    = T2 * K2 + N2
                    = T3 * K3 + N3

设n1是满足除以T1余N1的一个数，同样n2是满足除T2余N2的一个数，n3是满足除T3余N3的一个数，那么能不能使得
（n1+n2）除以T1余N1，进而使得（n1+n2+n3）除以T1余N1
                         使得（n1+n2+n3）除以T2余N2
                         使得（n1+n2+n3）除以T3余N3
由 a%b=c 则有 (a+kb)%b=c  得：
为使得（n1+n2+n3）除以T1余N1 ，n2和n3必须是T1的倍数
  使得（n1+n2+n3）除以T2余N2， n1和n3必须是T2的倍数
  使得（n1+n2+n3）除以T3余N3， n1和n2必须是T3的倍数
                         ↓
  n1是T2和T3的倍数，n2是T1和T3的倍数，n3是T1和T2的倍数
加上面条件
设n1是满足除以T1余N1的一个数，同样n2是满足除T2余N2的一个数，n3是满足除T3余N3的一个数
↓
以n1为例。并非直接从T2和T3的公倍数中找一个除T1余N1的数字，而是用了一点小技巧，先找一个除T1余1的数字再乘以N1
因为：
     若a%b=c 则(a*k)%b= a%b+a%b+...+a%b=c+c+...+c=kc

最后，n1+n2+n3只是问题的一个解并不是最小解。
如何得到最小解？只需从中最大限度的减掉T1 、T2、T3的最小公倍数即可
即若 a%b=c 则（a-kb）%b=c
所以   （n1+n2+n3）% (T1*T2*T3)就是最小解

例题：
问题描述poj1006

     人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。

问题分析

      首先我们要知道，任意两个峰值之间一定相距整数倍的周期。假设一年的第N天达到峰值，则下次达到峰值的时间为N+Tk(T是周期，k是任意正整数)。所以，三个峰值同时出现的那一天(S)应满足

      S = N1 + T1*k1 = N2 + T2*k2 = N3 + T3*k3

（正如刘未鹏，如何有效的记忆和学习一文中所说，养成习惯，经常主动回顾一段时间所学的东西，这儿不进有助于巩固长期记忆，而且一段时间之后的回忆你可能因为新的知识学习而对原来的知识有了进一步的看法，通过回顾可以整合新旧知识，得到新的启发。我们常常发现对知识的首次记忆往往是有偏颇的，或者只看到了一个方面，或者只是关注了一个点，一段时间之后再回来看往往能够和这段时间以来的新思考和知识结合起来，得到更多的东西。留心一下你会发现记忆实际上是是最脆弱的东西，而且我们首次对事物的理解几乎肯定是不深刻的。
全文链接http://mindhacks.cn/2009/03/28/effective-learning-and-memorization/）

5.使用素数的RSA算法
RSA公钥加密算法既是第一个能用于数据加密也能用于数字签名的算法。
什么是RSA ？
对于加密技术自己第一次接触到是在吴军的数学之美一书当中，当时一读此书顿时觉得数学和计算机科学到了作者那里真的就是一种美。关于密码学里面提到了《暗算》这部电视剧，于是赶紧迫不及待的百度了出来，一看便爱不释手。我至今没想明白为什么要起名曰：暗算，但是电视剧还是一部经典的电视剧，有兴趣的可以看一看。当时是怎么都没想明白公钥私钥是怎么回事，⊙﹏⊙b汗！，但是对于电视剧里那黑布隆冬的一屋子中老年男女在拿着算盘得得得的演算解密时，顿时被震惊了！

计算机中常用的加密技术分为两类，即对称加密和非对称加密。在对称加密技术中，对信息的加密和解密都是使用相同的密钥Key,也就是说，使用同一个密钥Key对数据进行加密和解密。这种加密方法可以简化加密的处理过程，信息交换双方都不必彼此研究和交换专用的解加密算法。如果在交换阶段，密钥没有泄露，那么加密数据的机密性和报文完整性就可以得到保证。但同时由于加密、解密都需要使用同一个Key，这样，信息传送双方都要接触到这个Key,密钥Key更容易泄露。

而非对称加密（又称为公开密钥加密）中，不再只有一个密钥Key了。密钥被分解成一对，一个称为公开密钥（简称公钥PK），另一个称为私有密钥（简称私钥SK）。对于公钥，可以通过非保密方式向他人公开，而私钥则由解密方保存，不用对别人公开。
RSA算法基础
在RSA算法中，最基础的一个定理就是RSA定理，这个定理描述如下：
   若P和Q是两个相异质数，另有正整数R和M，其中M的值与(P-1)(Q-1)的值互质，并使得(RM)mod(P-1)(Q-1)=1。有正整数A，且A<PQ,设：
   C=AR MOD PQ
   B=CM MOD PQ
则有A=B
RSA算法证明：

RSA操作步骤：
选择素数P、Q → N=PQ 
                    → T=(P-1)(Q-1)
                               → 选择E，E<T 且(E,T) 
                                          → 由DE Mod T=1 得到D
                                                    →得到公钥(N,E)、私钥(N,D)

发送信息的一方受到公钥PK之后，明文是M，加密后的密文为C，公钥(N,E)
         明文： M
         加密： ME MOD N=C
         密文： C
接收方持有私钥(N,D),在接收密文C后，即可通过私钥进行解密，
         密文： C
         解密： CD MOD N=M
         明文： M

关于数字签名技术的实现基础就是RSA加密技术，这里就不整理了。
关于RSA被破解的可能性


6.哥德巴赫猜想
     强哥德巴赫猜想：任一大于2的偶数都可以写成两个质数之和。
     弱哥德巴赫猜想：任一大于5的奇数都可以写成三个指数之和。

数值验证
    基本思路，设N为大于等于6的一个偶数，将其拆成两个数，分别检验是否为素数 
  for(int i=6;i<=n;i+=2){
        flag=1;
        for(j=2;j<=i/2;j++){
           if(j%2==0 || (i-j)%2==0)continue;//若一个加数是偶数，不判断素数
           if(prime[j]==1&&prime[i-j]==1){
                 printf("%d=%d+%d\n",i,j,i-j);
                 flag=0;
                 break;
           }
        }
        if(flag==1)printf("找到一个不符合要求的偶数：%d\n",i);       
  }
学习哥德巴赫猜想的意义，哥德巴赫猜想是用了简单枚举归纳推理提出来的。几百年前，德国数学家哥德巴赫发现了一个现象，一些奇数都分别等于三个素数之和，例如
17=3+3+11
41=11+13+17
77=7+17+53
……
哥德巴赫并没有吧所有的奇数都列举出来（也不可能列完），只是从少数例子出发就提出了一个猜想：所有大于5的奇数都可以分解为3个素数之和，这就是典型的“简单枚举归纳推理”。
在自己的学习生活中，也可以尝试着发现一些规律。

7.梅森素数
什么是梅森素数呢？
梅森素数是指形如 2p-1的正整数，其中指数P是素数，常记为Mp,若Mp是素数，则称为梅森素数。
M2=22-1=3       M2是梅森素数
M3=23-1=7       M3是梅森素数
M5=25-1=31      M5是梅森素数
M7=27-1=127     M7是梅森素数
M11=211-1=2047  M11不是梅森素数
……

关于素数，还有hash的地方要用到素数。


好了这一篇够长了，开下一篇文章好了。






















来自为知笔记(Wiz)


联系
我们