现在的位置: 首页 > 综合 > 正文

漫谈<<离散数学及其应用>> 第二章的计算机题目解答。 漫谈<<离散数学及其应用>> 第二章的计算机题目解答。

2019年05月01日 ⁄ 综合 ⁄ 共 10760字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

漫谈<<离散数学及其应用>> 第二章的计算机题目解答。

2012-03-12 10:00 26人阅读 评论(0) 收藏 举报

         第二章末尾的上机题目有很多道，其中和数论有关的是最值得做的:

12.已知两个正整数，用欧几里德算法求其最大公约数
13.已知两个正整数，用欧几里德算法求其最小公倍数
14.1 已知一个正整数，求n以内的素数
14.2已知一个整数，验证是否包含某个因子，检查m是否包含n的若干次方
14.已知一个正整数，求其素因子分解
15.已知一个正整数n和一个大于1的正整数b，求n的b进制展开
16.已知3个大于1的正整数a,b,n，求a^bmod m

17.已知一个正整数，求其康托展开
18.用线性同余(≡)发生器 x(n+1)=( a*x(n)+c) mod m, x(0)=b
生成一列n个伪随机数。
19.已知正整数a和b，求整数s和t使得sa+tb=gcd(a,b)
20.求同余幂
21.求中国余数问题方程组的解
22.模拟rsa编码解码
用VC实现的习题，运行通过。

[cpp] view
plaincopy

  1. #include "stdafx.h"  
  2. #include<algorithm>  
  3. #include<deque>  
  4. #include<iostream>  
  5. #include<ostream>  
  6. #include<map>  
  7. #include<math.h>  
  8. #include<vector>  
  9. #pragma warning(disable:4786)  
  10. using namespace std;  
  11. //12.已知两个正整数，用欧几里德算法求其最大公约数  
  12. int gcd(int m,int n){  
  13.     if(n==0)return 0;  
  14.     while(n){  
  15.         int temp=n;  
  16.         n=m%n;  
  17.         m=temp;  
  18.     }  
  19.     return m;  
  20. }//end gcd  
  21. //13.已知两个正整数，用欧几里德算法求其最小公倍数  
  22. int lcm(int m,int n){  
  23.     if(m==0||n==0)return 0;  
  24.     return m*n/gcd(m,n);  
  25. }  
  26. //14.1 已知一个正整数，求n以内的素数  
  27. vector<int> primes(int n){  
  28.     vector<int> vi;  
  29.     if(n==0){  
  30.         vi.push_back(0);  
  31.         return vi;  
  32.     }  
  33.     else if(n<0){  
  34.         vi.push_back(-1);  
  35.     }  
  36.     for(int i=2;i<n;++i){  
  37.         int s=vi.size();  
  38.         int c=0;  
  39.         for(;c<s;++c){  
  40.             if(gcd(i,vi[c])!=1)break;  
  41.         }  
  42.         if(c==s)  
  43.             vi.push_back(i);  
  44.     }  
  45.     return vi;  
  46. }  
  47. //14.2已知一个整数，验证是否包含某个因子，检查m是否包含n的若干次方  
  48. int contains(int m,int n){  
  49.     int mod=m%n;  
  50.     if(mod)return 0;//不能整除  
  51.     else{//整除  
  52.         int i=0;  
  53.         while(!mod){//可以继续除  
  54.             ++i;  
  55.             m/=n;  
  56.             mod=m%n;  
  57.             if(m==1)break;  
  58.         }  
  59.         return i;  
  60.     }  
  61. }  
  62. //14.已知一个正整数，求其素因子分解  
  63. map<int,int> divide(int n){  
  64.     map<int,int> mi;  
  65.     if(n==0 || n==1){  
  66.         mi[n]=1;  
  67.         return mi;  
  68.     }  
  69.     if(n<0){  
  70.         n=-n;  
  71.         mi[-1]=1;  
  72.     }  
  73.     int nsqrt=(int)sqrt(n);  
  74.     vector<int>& vi=primes(nsqrt);  
  75.     for(vector<int>::iterator it=vi.begin();it!=vi.end();++it){  
  76.         int mod=n%*it;//整除否  
  77.         if(!mod){//整除的  
  78.             mi[*it]=contains(n,*it);  
  79.         }  
  80.     }  
  81.     return mi;  
  82. }  
  83. void printDivide(const map<int,int>& mi){//打印素因子分解的结果  
  84.     for(map<int,int>::const_iterator it=mi.begin();it!=mi.end();++it){  
  85.         cout<<it->first<<'^'<<it->second<<',';  
  86.     }  
  87. }  
  88. void printExtend(const map<int,int>& mi){//康托展开  
  89.     for(map<int,int>::const_iterator it=mi.begin();it!=mi.end();++it){  
  90.         cout<<it->second<<'*'<<it->first<<"!+";  
  91.     }  
  92. }  
  93. //15.已知一个正整数n和一个大于1的正整数b，求n的b进制展开  
  94. deque<int> exp(int n,int b){  
  95.     deque<int> di;  
  96.     if(n<=0 || b<=1 || n<b){  
  97.         di.push_back(0);  
  98.         return di;  
  99.     }  
  100.     int d=1,m=0;  
  101.     do{  
  102.         d=n/b;  
  103.         m=n%b;  
  104.         di.push_front(m);  
  105.         n=d;  
  106.     }while(d);  
  107.     return di;  
  108. }  
  109. //16.已知3个大于1的正整数a,b,n，求a^b mod m  
  110. int powerDivide(int a,int b,int m){  
  111.     if(a<=0||b<=0||m<=0)return -1;  
  112.     if(a==1)return 1;  
  113.     if(b==1)return a%m;  
  114.     if(m==1)return 0;  
  115.     deque<int>& di=exp(b,2);  
  116.     reverse(di.begin(),di.end());  
  117.     int x=1;  
  118.     int power=a;  
  119.     for(deque<int>::iterator it=di.begin();it!=di.end();++it){  
  120.         if(*it==1){  
  121.             x*=power;  
  122.         }  
  123.         x%=m;  
  124.         power=(power*power)%m;  
  125.     }  
  126.     return x;  
  127. }  
  128. //17已知一个正整数，求其康托展开  
  129. map<int,int> extend(int n){  
  130.     map<int,int> mi;  
  131.     deque<int> di;  
  132.     if(n<=1)return mi;  
  133.     int i=1;  
  134.     int x=1;  
  135.     do{  
  136.         x*=i++;  
  137.         di.push_back(x);  
  138.     }while(x<n);  
  139.     di.pop_back();  
  140.   
  141.     for(int s=di.size()-1;s>=0;--s){  
  142.         int i=n/di[s];  
  143.         n-=i*di[s];  
  144.         mi[s+1]=i;  
  145.         if(n==0)break;  
  146.     }  
  147.     return mi;  
  148. }  
  149. //18已知正整数n,模数m，乘数a,增量c和种子x0,满足0≤a<m,0≤c<m,0≤x0<m，  
  150. //用线性同余(≡)发生器 x(n+1)=( a*x(n)+c ) mod m, x(0)=b 生成一列n个伪随机数。  
  151. //由上面的证明得到a=m+1,c和m互素  
  152.   
  153. //18.1 显然,n和m的关系必须满足n<=m。我们先生成一个m长度的序列。那么n长度的序列可以从m长度的序列得到  
  154. //通常m取一个很大的数  
  155. vector<int> xrand(int m){//例如x(n+1)=6*x(n)+3 mod 5, x0=1, 生成序列就应该是1,4,2,0,3,1  
  156.     vector<int> vr;  
  157.     if(m<=1)return vr;  
  158.     int a=m+1;  
  159.     vector<int>& vi=primes(m);  
  160.     int c;  
  161.     if(m==2)c=1;  
  162.     else{  
  163.         if(vi.back()==m-1)vi.pop_back();  
  164.         c=vi.back();  
  165.     }  
  166.       
  167.     int b=(a*c)%m;  
  168.     int xn=b;  
  169.     for(int i=0;i<m;++i){  
  170.         vr.push_back(xn);  
  171.         xn=((a*xn)+c)%m;  
  172.     }  
  173.     return vr;  
  174. }  
  175. /*19.已知正整数a和b，求整数s和t使得sa+tb=gcd(a,b) 
  176.  *注意第19题的推演方式。我们不但使用了自然数的四则运算，也使用了公式的层极展开。 
  177.  *一般的计算机语言本身并不能将一个函数(公式)本身作为计算的对象，所以需要我们先在 
  178.  *纸上求出一个递推公式，作为编程的基础。如果要动态的修改函数本身，就需要向脚本语言 
  179.  *或者函数式编程语言那样。 
  180.  *下面这个算法本身等同于广义欧几里德算法 
  181.  */  
  182. typedef pair<int,int> pi;  
  183. pi revert_gcd(int m,int n){  
  184.     pi p;  
  185.     if(n==0)return make_pair(0,0);  
  186.     if(m==n)return make_pair(1,0);  
  187.     deque<int> vi;  
  188.     bool less=(m<n);  
  189.     while(n){  
  190.         int temp=n;  
  191.         if(m>n){  
  192.             vi.push_back(m/n);  
  193.         }  
  194.         n=m%n;  
  195.         m=temp;  
  196.     }  
  197.     vi.pop_back();  
  198.     int x1=1;  
  199.     int x2=-vi.back();  
  200.     for(deque<int>::reverse_iterator it=vi.rbegin();it!=vi.rend();++it){  
  201.         vi.pop_front();  
  202.         if(vi.size()==0)break;  
  203.         int temp1=x2;  
  204.         int temp2=x1-(x2*vi.front());  
  205.         x1=temp1;  
  206.         x2=temp2;  
  207.     }  
  208.     if(less)swap(x1,x2);  
  209.     return make_pair(x1,x2);  
  210. }//end revert_gcd  
  211. //20.求同余幂  
  212. int rpower(int a,int m){  
  213.     if(gcd(a,m)!=1)return 0;  
  214.     int r=revert_gcd(a,m).first;  
  215.     return (r>0) ? r : r+m;  
  216. }  
  217. //21.求中国余数问题方程组的解  
  218. void rchina(vector<pi>& vp){//去掉a和m不互素的方程  
  219.     if(vp.size()==0)return;  
  220.     for(vector<pi>::iterator it=vp.begin();it!=vp.end();++it){  
  221.         int a=it->first;  
  222.         int m=it->second;  
  223.         if(a<=m){  
  224.             cout<<"rchina param error: a="<<a<<",m="<<m<<'\n';  
  225.         }  
  226.         int g=gcd(a,m);  
  227.         if(g!=1){  
  228.             vp.erase(it);  
  229.             vector<int>& vi=primes(a);  
  230.             for(vector<int>::iterator i=vi.begin();i!=vi.end();++i){  
  231.                 if(gcd(*i,m)==1)vp.push_back(make_pair(*i,m));//分解该方程为若干个小方程  
  232.             }  
  233.         }  
  234.     }  
  235. }  
  236. int solchina(vector<pi>& vp){  
  237.     rchina(vp);  
  238.     size_t len=vp.size();  
  239.     vector<int> via(len);  
  240.     vector<int> vim(len);  
  241.     vector<int> viy(len);  
  242.   
  243.     for(int i=0;i<len;++i){  
  244.         int a=vp[i].first;  
  245.         int m=vp[i].second;  
  246.         via[i]=a;  
  247.         vim[i]=1;  
  248.         for(int j=0;j<len;++j){  
  249.             if(i!=j)vim[i]*=m;  
  250.         }  
  251.         viy[i]=rpower(a,m);  
  252.     }  
  253.     int ret=0;  
  254.     int M=1;  
  255.     for(int k=0;k<len;++k){  
  256.         ret+=via[k]*vim[k]*viy[k];  
  257.         M*=vim[k];  
  258.     }  
  259.     return ret%M;  
  260. }  
  261. //22.模拟rsa编码解码  
  262. int p=43;  
  263. int q=59;  
  264. int e=13;  
  265. int d=rpower(e,(p-1)*(q-1));  
  266. int encode(int m){  
  267.     return powerDivide(m,e,p*q);  
  268. }  
  269. int decode(int c){  
  270.     return powerDivide(c,d,p*q);  
  271. }  
  272. void printDecode(vector<int>& vi){  
  273.     for(vector<int>::iterator it=vi.begin();it!=vi.end();++it){  
  274.         int m=decode(*it);  
  275.         char buf[1024]={0};  
  276.         itoa(m,buf,10);  
  277.         cout<<buf<<',';  
  278.     }  
  279. }  
  280. int main(int argc, char* argv[])  
  281. {  
  282.     int g=gcd(153460,12233440);  
  283.     int l=lcm(27,33);  
  284.     vector<int>& vi=primes(5);  
  285.     copy(vi.begin(),vi.end(),ostream_iterator<int>(cout,","));  
  286.     cout<<'\n';  
  287.     printDivide(divide(-720));  
  288.     deque<int>& di=exp(111,8);  
  289.     cout<<"\n111 mod 8=\n";  
  290.     copy(di.begin(),di.end(),ostream_iterator<int>(cout,""));  
  291.     cout<<'\n';  
  292.     cout<<"\n2^9 mod 5 ="<<powerDivide(2,9,5)<<'\n';  
  293.     map<int,int>& me=extend(10);  
  294.     printExtend(me);  
  295.     vector<int>& vr=xrand(12);  
  296.     cout<<'\n';  
  297.     copy(vr.begin(),vr.end(),ostream_iterator<int>(cout,","));  
  298.     cout<<'\n';  
  299.     pi& p=revert_gcd(252,198);  
  300.     cout<<"\ngcd(252,198)="<<gcd(252,198)<<'='<<"252*("<<p.first<<")+198*("<<p.second<<")\n";  
  301.     cout<<"rpower(3,7)="<<rpower(3,7)<<'\n';  
  302.     vector<int> v;  
  303.     v.push_back(0667);  
  304.     v.push_back(1947);  
  305.     v.push_back(0671);  
  306.     printDecode(v);  
  307.     return 0;  
  308. }  

运行后输出:

2,3,
-1^1,2^4,3^2,5^1,
111 mod 8=
157

2^9 mod 5 =2
2*2!+1*3!+
7,2,9,4,11,6,1,8,3,10,5,0,

gcd(252,198)=18=252*(4)+198*(-5)
rpower(3,7)=5
1579,1475,1288

--------------------------------------------------------------------------

还有几个习题中出现的上机算法题，也都用VC2010实现。几种常见的排序算法

[cpp] view
plaincopy

  1. #include "stdafx.h"  
  2. #include<algorithm>  
  3. #include<iostream>  
  4. #include<iterator>  
  5. #include<functional>  
  6. using namespace std;  
  7.   
  8. //冒泡排序  
  9. template<typename Func>  
  10. void bubleSort(int* pv,int count,Func f){  
  11.     for(int i=0;i<count-1;++i){  
  12.         for(int j=0;j<count-1-i;++j){  
  13.             if( !f(pv[j],pv[j+1]))swap(pv[j],pv[j+1]);  
  14.         }  
  15.     }  
  16. }  
  17.   
  18. //插入排序  
  19. template<typename Func>  
  20. void InsertSort( int *pSortDest, int *pSortSrc, size_t nSort, Func compare )  
  21. {  
  22.     if( pSortDest == NULL || pSortSrc == NULL || nSort == 0 )  
  23.     {  
  24.         return;  
  25.     }  
  26.     size_t nDone = 0;  
  27.     while( nSort )  
  28.     {  
  29.         int& nNext = pSortSrc[ nDone ];//会为nNext生成一个指针  
  30.         size_t L = 0;  
  31.         for( ; L < nDone; ++L )  
  32.         {  
  33.             if( ! compare(nNext, pSortDest[ L ]) )  
  34.             {  
  35.                 continue;  
  36.             }  
  37.             else  
  38.             {  
  39.                 break;  
  40.             }  
  41.         }  
  42.         //L现在就是插入的位置  
  43.   
  44.         for( size_t move = nDone; move > L ; --move )  
  45.         {  
  46.             pSortDest[ move ] = pSortDest[ move - 1 ];  
  47.         }  
  48.         pSortDest[ L ] = nNext;  
  49.         --nSort;  
  50.         ++nDone;  
  51.     }//返回一个引用，减少一次ctor.  
  52. }  
  53.   
  54. template<typename Func>//二分插入排序  
  55. void BinaryInsertSort( int *pSortDest, int *pSortSrc, size_t nSort, Func compare )  
  56. {  
  57.     if( pSortDest == NULL || pSortSrc == NULL || nSort == 0 )  
  58.     {  
  59.         return;  
  60.     }  
  61.     size_t nDone = 0;  
  62.     while( nSort )  
  63.     {  
  64.         int& nNext = pSortSrc[ nDone ];  
  65.         size_t L = 0;  
  66.         size_t begin=0;  
  67.         size_t end=nDone;  
  68.         size_t middle = (begin+end)/2;  
  69.   
  70.         for(;;){  
  71.             if( compare(nNext, pSortDest[ middle ] ) )  
  72.             {  
  73.                 end=middle;  
  74.             }  
  75.             else  
  76.             {  
  77.                 begin=middle;  
  78.             }  
  79.             middle=(begin+end)/2;  
  80.             if(middle==begin)break;  
  81.             if(middle==end)break;  
  82.         }  
  83.         L=end;  
  84.         //L现在就是插入的位置  
  85.   
  86.         for( size_t move = nDone; move > L ; --move )  
  87.         {  
  88.             pSortDest[ move ] = pSortDest[ move - 1 ];  
  89.         }  
  90.         pSortDest[ L ] = nNext;  
  91.         --nSort;  
  92.         ++nDone;  
  93.     }//返回一个引用，减少一次ctor.  
  94. }  
  95.   
  96. int main(void){  
  97.     int ToSort[]={8,3,2,7,6,1,5};  
  98.     bubleSort(ToSort,7,less<int>());  
  99.     copy(ToSort,ToSort+7,ostream_iterator<int>(cout,","));  
  100.     cout<<endl;  
  101.   
  102.     int src[]={8,3,2,7,6};  
  103.     int dest[5];  
  104.     InsertSort(dest,src,5,less<int>());  
  105.     copy(dest,dest+5,ostream_iterator<int>(cout,","));  
  106.     cout<<endl;  
  107.   
  108.     int src2[]={3,2,4};  
  109.     int dest2[3];  
  110.     BinaryInsertSort(dest2,src2,3,less<int>());  
  111.     copy(dest2,dest2+3,ostream_iterator<int>(cout,","));  
  112.   
  113.     return 0;  
  114. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞