05_數(shù)論

1、藍橋杯 全國軟件大賽輔導教程,天農(nóng)計算機系 許曉華,數(shù)論,素數(shù)組素數(shù)找素數(shù)篩法求素數(shù)孿生素數(shù)金蟬素數(shù)公約數(shù)與公倍數(shù)歐幾里德算法有理數(shù)類進制轉換N進制轉換為10進制10進制轉換為N進制地址轉換10進制正小數(shù)轉換為其他進制,判斷是否為素數(shù),#include #include using namespace std;int isprime(int n){for(int i=2;i<=sqrt(n)

2、;i++){if(n%i==0) return 0;}return 1;}int main(){cout<<isprime(17);return 0;},#include using namespace std;int isprime(int n){for(int i=2;i*i<=n;i++){if(n%i==0) return 0;}return 1;

3、}int main(){cout<<isprime(17);return 0;},或,組素數(shù)2013第四屆Java預賽高職第2題,素數(shù)就是不能再進行等分的數(shù)。比如：2 3 5 7 11 等。 9 = 3 * 3 說明它可以3等分，因而不是素數(shù)。 我們國家在1949年建國。如果只給你 1 9 4 9 這4個數(shù)字卡片，可以隨意擺放它們的先后順序（但卡片不能倒著擺放啊，我們不是在腦筋急轉彎?。?，那

4、么，你能組成多少個4位的素數(shù)呢？ 比如：1949，4919 都符合要求。請你提交：能組成的4位素數(shù)的個數(shù)，不要羅列這些素數(shù)!!,#include using namespace std;int isprime(int n){for(int i=2;i*i<n;i++){if(n%i==0) return 0;}return 1;}int main(){int a,b,c,d,sum=

5、0;int m[4]={1,9,9,4};for(a=0;a<4;a++)for(b=0;b<4;b++)for(c=0;c<4;c++)for(d=0;d<3;d++){if(a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d){if(isprime(m[a]*1000+

6、m[b]*100+m[c]*10+m[d]))sum++;}}cout<<sum;return 0;},答案：12,全排列的解法,#include #define N 4//對4個數(shù)進行全排列int sum=0;int isprime(int x){int i;for(i=2;i*i<=x;i++){if(x%i==0)return 0;}retur

7、n 1;}void perms(int p[],int start){int i,t;if(start==N-1){if(isprime(p[0]*1000+p[1]*100+p[2]*10+p[3]))sum++;return;}for(i=start;i<N;i++) // 注意i從start開始，不從0開始{t=p[i];p[i]=p[start];p[start]=t

8、;//交換perms(p,start+1);//遞歸t=p[i];p[i]=p[start];p[start]=t;//交換回來}}int main(){int p[N]={1,9,4,9};perms(p,0);//從數(shù)組中索引號為0的元素開始進行排列printf("%d",sum);return 0;},找素數(shù)(12分)2012決賽C高職第1題,素數(shù)就是不能再進行等分

9、的整數(shù)。比如：7，11。而9不是素數(shù)，因為它可以平分為3等份。一般認為最小的素數(shù)是2，接著是3，5，... 請問，第100002(十萬零二)個素數(shù)是多少？ 請注意：“2” 是第一素數(shù)，“3” 是第二個素數(shù)，依此類推。 不需要提交源代碼，只要寫出準確的結果即可！,,題目可能改編自歐拉計劃第7題,,#include int isPrime(int n){int i;for(i=2;i*i<=

10、n;i++){if(n%i==0) return 0;}return 1;}int main(){ int i,n=1;//第1個素數(shù)是2 for (i=3; ;i+=2)//從3開始判斷 { if(isPrime(i)) n++; if(n==100002) break; } printf("%d\n",i);

11、 return 0;},更快的算法？,求第10萬零2個，基本可以秒殺。但求第100萬零2個呢？要等10幾秒才出結果。有沒有效率更高的方法？有篩法！,篩法求素數(shù),#include #define N 10000000//篩法，求1000萬以內(nèi)的所有素數(shù) int a[N];int main(){int i,j,sum=0;for(i=2;i<N/2;i++){if(a[i]) continue

12、;//合數(shù)不參加篩法 for(j=2*i;j<=N;j+=i){a[j]=1;}}for(i=2;i<N;i++){if(!a[i]) {sum++;if(100002==sum) break;}}printf("%d",i);return 0;},孿生素數(shù)（4分）2011預賽Java本科第2題,所謂孿生素數(shù)指的就是間

13、隔為 2 的相鄰素數(shù)，它們之間的距離已經(jīng)近得不能再近了，就象孿生兄弟一樣。最小的孿生素數(shù)是 (3, 5)，在 100 以內(nèi)的孿生素數(shù)還有 (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) 和 (71, 73)，總計有 8 組。但是隨著數(shù)字的增大，孿生素數(shù)的分布變得越來越稀疏，尋找孿生素數(shù)也變得越來越困難。那么會不會在超過某個界限之后就再也不存在孿生素數(shù)了呢？孿生素數(shù)有無窮

14、多對！這個猜想被稱為孿生素數(shù)猜想，至今沒有被嚴格證明。但借助于計算機我們確實可以找到任意大數(shù)范圍內(nèi)的所有孿生素數(shù)對。下面的代碼求出了正整數(shù)n以內(nèi)（不含n）的所有孿生素數(shù)對的個數(shù)。比如，當n=100的時候，該方法返回8。,public static boolean isPrime(int x){for(int i=2; i<=x/2; i++){if(x%i==0) _____________;}

15、return true;}public static int twinPrimeNum(int n){int sum = 0;for(int i=2; i<n; i++){if(isPrime(i) && ___________) sum++;}return sum;},評分標準,/* 答案： 空1： return false 空2： i

16、sPrime(i+2) && i+21 && isPrime(i-2)) 注意：僅回答 isPrime(i-2) 不給分*/,金蟬素數(shù)2013第四屆決賽Java高職第3題,考古發(fā)現(xiàn)某古墓石碑上刻著一個數(shù)字：13597，后研究發(fā)現(xiàn)： 這是一個素數(shù)！ 并且，去掉首尾數(shù)字仍是素數(shù)！ 并且，最中間的數(shù)字也是素數(shù)！ 這樣特征的數(shù)字還有哪些呢？通過以下程序的幫助可以輕松

17、解決。請仔細閱讀代碼，并填寫劃線部分缺失的代碼。,public class A{static boolean isPrime(int n){if(n<=1) return false;for(int i=2; i*i<=n; i++){if(n%i==0) return false;}return true;}static void f(int[] x, int k){

18、if(_____________________________){ // 填空位置if(isPrime(x[0]*10000 + x[1]*1000 + x[2]*100 + x[3]*10 + x[4]) &&isPrime(x[1]*100 + x[2]*10 + x[3]) &&isPrime(x[2]))System.out.println("

19、;"+x[0]+x[1]+x[2]+x[3]+x[4]);return;}for(int i=k; i<x.length; i++){{int tmp=x[k]; x[k]=x[i]; x[i]=tmp; }f(x,k+1);{int tmp=x[k]; x[k]=x[i]; x[i]=tmp; }}}static void test(){int[

20、] x = {1,3,5,7,9};f(x,0);}public static void main(String[] args){test();}},k==4或k==5都可以,又是全排列,最大公約數(shù)(gcd)greatest common divisor,《計算機程序設計藝術》里講的第一個算法就是求gcd的算法。采用輾轉相除法，又名歐幾里德算法,輾轉相除法求最大公約數(shù)非遞歸實現(xiàn),#include i

21、nt gcd(int x,int y){int t;while(y){t=x%y;x=y;y=t;}return x;}int main(){int x=48,y=36;printf("%d",gcd(x,y)); return 0;},輾轉相除法求最大公約數(shù)遞歸實現(xiàn),#include int gcd(int x,int y){return y?g

22、cd(y,x%y):x;}int main(){int x=48,y=36;printf("%d",gcd(x,y)); return 0;},#include int gcd(int x,int y){if(y) return gcd(y,x%y);else return x;}int main(){int x=48,y=36;printf("%d"

23、,gcd(x,y)); return 0;},有理數(shù)類(6分)2013第四屆Java高職第5題,,答案與測評程序,此題用到了求最大公約數(shù)答案：new Rational(ra*x.rb + rb*x.ra, rb*x.rb),Java的BigInteger類包含gcd函數(shù),import java.math.BigInteger;public class Main{public static void main(Str

24、ing[] args){BigInteger b=BigInteger.valueOf(36);BigInteger n=b.gcd(BigInteger.valueOf(48));System.out.println(n);}},最小公倍數(shù)(lcm) Least Common Multiple,第1種算法：lcm(a,b) = a*b/gcd(a,b),公約數(shù)公倍數(shù)2013第四

25、屆預賽C/C++高職第5題,我們經(jīng)常會用到求兩個整數(shù)的最大公約數(shù)和最小公倍數(shù)的功能。 下面的程序給出了一種算法。 函數(shù) myfunc 接受兩個正整數(shù)a,b 經(jīng)過運算后打印出 它們的最大公約數(shù)和最小公倍數(shù)。 此時，調(diào)用 myfunc(15,20) 將會輸出：360,,// 交換數(shù)值void swap(int *a,int *b){ int temp; temp=*a; *a=*

26、b; *b=temp;}void myfunc(int a, int b){ int m,n,r; if(a<b) swap(&a,&b); m=a;n=b;r=a%b; while(r!=0) { a=b;b=r; r=a%b; } printf("%d\n",b); // 最大公約數(shù) printf("

27、;%d\n", ____________________________________); // 最小公倍數(shù) },答案：m*n/b,最小公倍數(shù)(lcm) Least Common Multiple,第2種算法：見下一道題,最小公倍數(shù)2011預賽C高職第3題,代碼填空 （滿分3分）求兩個數(shù)字的最小公倍數(shù)是很常見的運算。比如，3和5的最小公倍是15。6和8的最小公倍數(shù)是24。下面的代碼對給定

28、的兩個正整數(shù)求它的最小公倍數(shù)。請?zhí)顚懭鄙俚拇a，使程序盡量高效地運行。把填空的答案（僅填空處的答案，不包括題面）存入考生文件夾下對應題號的“解答.txt”中即可。int f(int a, int b){int i;for(i=a;;______){if(i%b==0) return i;}},答案：i+=a,核桃的數(shù)量2013第四屆C高職第7題,小張是軟件項目經(jīng)理，他帶領3個開發(fā)組。工期緊，今天都在加班呢

29、。為鼓舞士氣，小張打算給每個組發(fā)一袋核桃（據(jù)傳言能補腦）。他的要求是： 1. 各組的核桃數(shù)量必須相同 2. 各組內(nèi)必須能平分核桃（當然是不能打碎的） 3. 盡量提供滿足1,2條件的最小數(shù)量（節(jié)約鬧革命嘛）程序從標準輸入讀入：a b ca,b,c都是正整數(shù)，表示每個組正在加班的人數(shù)，用空格分開（a,b,c<30）程序輸出：一個正整數(shù)，表示每袋核桃的數(shù)量。例如：用戶輸入：2 4 5程序輸出：

30、20再例如：用戶輸入：3 1 1程序輸出：3,代碼,#include int main(){int a,b,c,i;scanf("%d%d%d",&a,&b,&c);for(i=a;;i+=a){if(i%b==0&&i%c==0)break;}printf("%d",i);return 0;},進制轉

31、換—N進制轉10進制,方法見下一題,官網(wǎng)2011模擬題第2題代碼填空（滿分3分）,下列代碼把一個二進制的串轉換為整數(shù)。請?zhí)顚懭鄙俚恼Z句；char* p = "1010110001100";int n = 0;for(int i=0;i<strlen(p); i++){n = _________________;}printf("%d\n", n);,答案：n

32、*2+p[i]-'0'或(n<<1)+p[i]-’0’,N進制轉10進制，都用這種算法，2進制這里是n*2，N進制就是n*N,可運行的代碼,#include #include "string.h"int main(int argc, char* argv[]){char* p = "1010110001100";int n = 0;for(int i

33、=0;i<strlen(p); i++){n = (n<<1)+p[i]-'0';}printf("%d\n", n);return 0;},10進制轉N進制,先%再/,十進制轉十六進制,//C++#include using namespace std;string h="0123456789ABCDEF";void f(int

34、 x){string s="";while(x){s=h[x%16]+s;x/=16;}cout<<s;}int main(){f(254);return 0;},十進制轉十六進制,//Javapublic class Main{public static void main(String[] args){dec2Hex(254);}

35、public static void dec2Hex(int dec){ char[] ch = {'0','1','2','3','4','5','6','7','8','9','A','B','C',&#

36、39;D','E','F'}; String hex = ""; while (dec != 0) { hex = ch[dec & 15]+hex; dec = dec >> 4; } System.out.println(

37、hex);}},十進制轉十六進制(遞歸),C/C++版,#include using namespace std;string h="0123456789ABCDEF";void f(int x){if(x>=16) f(x>>4);cout<<h[x&15];}int main(){f(254);return 0;},十進制轉十六進制(遞歸

38、),Java版,public class Main{static char []ch = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','

39、;E','F'};static void f(int n){ if(n>=16) f(n>>4); System.out.print(ch[n&15]);} public static void main(String args[]) { f(254); }},2011 模擬 java 本科第6題,下列代碼把16進制表示的串轉換為3進制表

40、示的串。試完善之。例如：x=“5”則返回：“12”又例如：x=”F”則返回：“120”,private static int getRealValue(char x){if(x>='0' && x='a' && x='A' && x<='F') return x-'A'+10;

41、return 0;}public static String jin_zhi_16_3(String x){int n = 0; // 累加真值for(int i=0; i<x.length(); i++){n = _________ + getRealValue(x.charAt(i)); // 填空}String t = "";for(;;)

42、{if(n==0) break;t = (n % 3) + t; _____________; // 填空}return t;},答案與可運行代碼,n*16n/=3,10進制小數(shù)轉N進制小數(shù),“乘N取整，順序排列”對十進制小數(shù)乘N得到的整數(shù)部分和小數(shù)部分，取整數(shù)部分，剩下的小數(shù)部分繼續(xù)循環(huán)乘N取整例如：0.25轉成二進制0.25*2=0.5 取整是00.5*2=1.0 取整是

43、1即0.25的二進制為 0.01,N進制小數(shù)轉10進制小數(shù),比如10.101的二進制..對應十進制為1*(2^1)+0*(2^0)+1*(2^-1)+0*(2^-2)+1*(2^-3),N進制小數(shù)(5分)2011預賽C本科第4題,將任意十進制正小數(shù)分別轉換成2,3,4,5,6,7,8,9進制正小數(shù)，小數(shù)點后保留8位，并輸出。例如：若十進制小數(shù)為0.795，則輸出：十進制正小數(shù) 0.795000 轉換成 2 進制數(shù)為: 0.11

44、001011十進制正小數(shù) 0.795000 轉換成 3 進制數(shù)為: 0.21011011十進制正小數(shù) 0.795000 轉換成 4 進制數(shù)為: 0.30232011十進制正小數(shù) 0.795000 轉換成 5 進制數(shù)為: 0.34414141十進制正小數(shù) 0.795000 轉換成 6 進制數(shù)為: 0.44341530十進制正小數(shù) 0.795000 轉換成 7 進制數(shù)為: 0.53645364十進制正小數(shù) 0.795

45、000 轉換成 8 進制數(shù)為: 0.62702436十進制正小數(shù) 0.795000 轉換成 9 進制數(shù)為: 0.71348853以下代碼提供了這個功能。其中，dTestNo表示待轉的十進制小數(shù)。iBase表示進制數(shù)。請?zhí)顚懭笔У牟糠帧?void fun(double dTestNo, int iBase){int iT[8];int iNo;printf("十進制正小數(shù) %f 轉換成 %d 進制數(shù)為: &q

46、uot;,dTestNo, iBase);for(iNo=0;iNo<8;iNo++){dTestNo *= iBase;iT[iNo] = ________________;if(___________________) dTestNo -= iT[iNo];}printf("0.");for(iNo=0; iNo<8; iNo++) printf("%d

47、", iT[iNo]);printf("\n");}void main ( ){double dTestNo= 0.795;int iBase;for(iBase=2;iBase<=9;iBase++)fun(dTestNo,iBase);printf("\n");},,#include "stdio.h"void fun(

48、double dTestNo, int iBase){int iT[8];int iNo;printf("十進制正小數(shù) %f 轉換成 %d 進制數(shù)為: ",dTestNo, iBase);for(iNo=0;iNo=1.0) dTestNo -= iT[iNo]; // 填空2}printf("0.");for(iNo=0; iNo<8; iNo++) pri

49、ntf("%d", iT[iNo]);printf("\n");}int main (int argc, char* argv[]){double dTestNo= 0.795;int iBase;for(iBase=2;iBase<=9;iBase++)fun(dTestNo,iBase);printf("\n");return 0

50、;},兩個作業(yè),地址轉換十六進制轉八進制,地址轉換2012決賽C高職第3題(19分) 2012決賽Java高職第4題(21分),Excel是最常用的辦公軟件。每個單元格都有唯一的地址表示。比如：第12行第4列表示為：“D12”，第5行第255列表示為“IU5”。事實上，Excel提供了兩種地址表示方法，還有一種表示法叫做RC格式地址。 第12行第4列表示為：“R12C4”，第5行第255列表示為“R5C255”。 你的任務是

51、：編寫程序，實現(xiàn)從RC地址格式到常規(guī)地址格式的轉換。【輸入、輸出格式要求】 用戶先輸入一個整數(shù)n（n<100），表示接下來有n行輸入數(shù)據(jù)。 接著輸入的n行數(shù)據(jù)是RC格式的Excel單元格地址表示法。 程序則輸出n行數(shù)據(jù)，每行是轉換后的常規(guī)地址表示法。 例如：用戶輸入：2R12C4R5C255 則程序應該輸出：D12IU5,測試用例與運行結果,,6R1C1R65535C256

52、R100C100R100C99R1C255R255C27,A1IV65535CV100CU100IU1AA255,作業(yè)評測系統(tǒng) BASIC-12:十六進制轉八進制,問題描述　　給定n個十六進制正整數(shù)，輸出它們對應的八進制數(shù)。輸入格式　　輸入的第一行為一個正整數(shù)n （1<=n<=10）?！　〗酉聛韓行，每行一個由0~9、大寫字母A~F組成的字符串，表示要轉換的十六進制正整數(shù)，每個十六進制數(shù)長度不超過1

53、00000。輸出格式　　輸出n行，每行為輸入對應的八進制正整數(shù)。注意　　輸入的十六進制數(shù)不會有前導0，比如012A?！　≥敵龅陌诉M制數(shù)也不能有前導0。樣例輸入239123ABC樣例輸出714435274提示　　先將十六進制數(shù)轉換成某進制數(shù)，再由某進制數(shù)轉換成八進制。,,因為要轉換的16進制整數(shù)太大，所以，不能借助10進制轉8進制。需要借助2進制,代碼,32行,[ Add your company sloga