版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、藍(lán)橋杯 全國軟件大賽輔導(dǎo)教程,天農(nóng)計(jì)算機(jī)系 許曉華,數(shù)論,素?cái)?shù)組素?cái)?shù)找素?cái)?shù)篩法求素?cái)?shù)孿生素?cái)?shù)金蟬素?cái)?shù)公約數(shù)與公倍數(shù)歐幾里德算法有理數(shù)類進(jìn)制轉(zhuǎn)換N進(jìn)制轉(zhuǎn)換為10進(jìn)制10進(jìn)制轉(zhuǎn)換為N進(jìn)制地址轉(zhuǎn)換10進(jìn)制正小數(shù)轉(zhuǎn)換為其他進(jìn)制,判斷是否為素?cái)?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;},或,組素?cái)?shù)2013第四屆Java預(yù)賽高職第2題,素?cái)?shù)就是不能再進(jìn)行等分的數(shù)。比如:2 3 5 7 11 等。 9 = 3 * 3 說明它可以3等分,因而不是素?cái)?shù)。 我們國家在1949年建國。如果只給你 1 9 4 9 這4個(gè)數(shù)字卡片,可以隨意擺放它們的先后順序(但卡片不能倒著擺放啊,我們不是在腦筋急轉(zhuǎn)彎?。?,那
4、么,你能組成多少個(gè)4位的素?cái)?shù)呢? 比如:1949,4919 都符合要求。請你提交:能組成的4位素?cái)?shù)的個(gè)數(shù),不要羅列這些素?cái)?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個(gè)數(shù)進(jìn)行全排列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的元素開始進(jìn)行排列printf("%d",sum);return 0;},找素?cái)?shù)(12分)2012決賽C高職第1題,素?cái)?shù)就是不能再進(jìn)行等分
9、的整數(shù)。比如:7,11。而9不是素?cái)?shù),因?yàn)樗梢云椒譃?等份。一般認(rèn)為最小的素?cái)?shù)是2,接著是3,5,... 請問,第100002(十萬零二)個(gè)素?cái)?shù)是多少? 請注意:“2” 是第一素?cái)?shù),“3” 是第二個(gè)素?cái)?shù),依此類推。 不需要提交源代碼,只要寫出準(zhǔn)確的結(jié)果即可!,,題目可能改編自歐拉計(jì)劃第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個(gè)素?cái)?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個(gè),基本可以秒殺。但求第100萬零2個(gè)呢?要等10幾秒才出結(jié)果。有沒有效率更高的方法?有篩法!,篩法求素?cái)?shù),#include #define N 10000000//篩法,求1000萬以內(nèi)的所有素?cá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;},孿生素?cái)?shù)(4分)2011預(yù)賽Java本科第2題,所謂孿生素?cái)?shù)指的就是間
13、隔為 2 的相鄰素?cái)?shù),它們之間的距離已經(jīng)近得不能再近了,就象孿生兄弟一樣。最小的孿生素?cái)?shù)是 (3, 5),在 100 以內(nèi)的孿生素?cái)?shù)還有 (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) 和 (71, 73),總計(jì)有 8 組。但是隨著數(shù)字的增大,孿生素?cái)?shù)的分布變得越來越稀疏,尋找孿生素?cái)?shù)也變得越來越困難。那么會(huì)不會(huì)在超過某個(gè)界限之后就再也不存在孿生素?cái)?shù)了呢?孿生素?cái)?shù)有無窮
14、多對!這個(gè)猜想被稱為孿生素?cái)?shù)猜想,至今沒有被嚴(yán)格證明。但借助于計(jì)算機(jī)我們確實(shí)可以找到任意大數(shù)范圍內(nèi)的所有孿生素?cái)?shù)對。下面的代碼求出了正整數(shù)n以內(nèi)(不含n)的所有孿生素?cái)?shù)對的個(gè)數(shù)。比如,當(dāng)n=100的時(shí)候,該方法返回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;},評分標(biāo)準(zhǔn),/* 答案: 空1: return false 空2: i
16、sPrime(i+2) && i+21 && isPrime(i-2)) 注意:僅回答 isPrime(i-2) 不給分*/,金蟬素?cái)?shù)2013第四屆決賽Java高職第3題,考古發(fā)現(xiàn)某古墓石碑上刻著一個(gè)數(shù)字:13597,后研究發(fā)現(xiàn): 這是一個(gè)素?cái)?shù)! 并且,去掉首尾數(shù)字仍是素?cái)?shù)! 并且,最中間的數(shù)字也是素?cái)?shù)! 這樣特征的數(shù)字還有哪些呢?通過以下程序的幫助可以輕松
17、解決。請仔細(xì)閱讀代碼,并填寫劃線部分缺失的代碼。,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,《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》里講的第一個(gè)算法就是求gcd的算法。采用輾轉(zhuǎn)相除法,又名歐幾里德算法,輾轉(zhuǎn)相除法求最大公約數(shù)非遞歸實(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;},輾轉(zhuǎn)相除法求最大公約數(shù)遞歸實(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、屆預(yù)賽C/C++高職第5題,我們經(jīng)常會(huì)用到求兩個(gè)整數(shù)的最大公約數(shù)和最小公倍數(shù)的功能。 下面的程序給出了一種算法。 函數(shù) myfunc 接受兩個(gè)正整數(shù)a,b 經(jīng)過運(yùn)算后打印出 它們的最大公約數(shù)和最小公倍數(shù)。 此時(shí),調(diào)用 myfunc(15,20) 將會(huì)輸出: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預(yù)賽C高職第3題,代碼填空 (滿分3分)求兩個(gè)數(shù)字的最小公倍數(shù)是很常見的運(yùn)算。比如,3和5的最小公倍是15。6和8的最小公倍數(shù)是24。下面的代碼對給定
28、的兩個(gè)正整數(shù)求它的最小公倍數(shù)。請?zhí)顚懭鄙俚拇a,使程序盡量高效地運(yùn)行。把填空的答案(僅填空處的答案,不包括題面)存入考生文件夾下對應(yīng)題號的“解答.txt”中即可。int f(int a, int b){int i;for(i=a;;______){if(i%b==0) return i;}},答案:i+=a,核桃的數(shù)量2013第四屆C高職第7題,小張是軟件項(xiàng)目經(jīng)理,他帶領(lǐng)3個(gè)開發(fā)組。工期緊,今天都在加班呢
29、。為鼓舞士氣,小張打算給每個(gè)組發(fā)一袋核桃(據(jù)傳言能補(bǔ)腦)。他的要求是: 1. 各組的核桃數(shù)量必須相同 2. 各組內(nèi)必須能平分核桃(當(dāng)然是不能打碎的) 3. 盡量提供滿足1,2條件的最小數(shù)量(節(jié)約鬧革命嘛)程序從標(biāo)準(zhǔn)輸入讀入:a b ca,b,c都是正整數(shù),表示每個(gè)組正在加班的人數(shù),用空格分開(a,b,c<30)程序輸出:一個(gè)正整數(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;},進(jìn)制轉(zhuǎn)
31、換—N進(jìn)制轉(zhuǎn)10進(jìn)制,方法見下一題,官網(wǎng)2011模擬題第2題代碼填空(滿分3分),下列代碼把一個(gè)二進(jìn)制的串轉(zhuǎn)換為整數(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進(jìn)制轉(zhuǎn)10進(jìn)制,都用這種算法,2進(jìn)制這里是n*2,N進(jìn)制就是n*N,可運(yù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進(jìn)制轉(zhuǎn)N進(jìn)制,先%再/,十進(jìn)制轉(zhuǎn)十六進(jì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;},十進(jìn)制轉(zhuǎn)十六進(jìn)制,//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);}},十進(jìn)制轉(zhuǎn)十六進(jìn)制(遞歸),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;},十進(jìn)制轉(zhuǎn)十六進(jìn)制(遞歸
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進(jìn)制表示的串轉(zhuǎn)換為3進(jìn)制表
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;},答案與可運(yùn)行代碼,n*16n/=3,10進(jìn)制小數(shù)轉(zhuǎn)N進(jìn)制小數(shù),“乘N取整,順序排列”對十進(jìn)制小數(shù)乘N得到的整數(shù)部分和小數(shù)部分,取整數(shù)部分,剩下的小數(shù)部分繼續(xù)循環(huán)乘N取整例如:0.25轉(zhuǎn)成二進(jìn)制0.25*2=0.5 取整是00.5*2=1.0 取整是
43、1即0.25的二進(jìn)制為 0.01,N進(jìn)制小數(shù)轉(zhuǎn)10進(jìn)制小數(shù),比如10.101的二進(jìn)制..對應(yīng)十進(jìn)制為1*(2^1)+0*(2^0)+1*(2^-1)+0*(2^-2)+1*(2^-3),N進(jìn)制小數(shù)(5分)2011預(yù)賽C本科第4題,將任意十進(jìn)制正小數(shù)分別轉(zhuǎn)換成2,3,4,5,6,7,8,9進(jìn)制正小數(shù),小數(shù)點(diǎn)后保留8位,并輸出。例如:若十進(jìn)制小數(shù)為0.795,則輸出:十進(jìn)制正小數(shù) 0.795000 轉(zhuǎn)換成 2 進(jìn)制數(shù)為: 0.11
44、001011十進(jìn)制正小數(shù) 0.795000 轉(zhuǎn)換成 3 進(jìn)制數(shù)為: 0.21011011十進(jìn)制正小數(shù) 0.795000 轉(zhuǎn)換成 4 進(jìn)制數(shù)為: 0.30232011十進(jìn)制正小數(shù) 0.795000 轉(zhuǎn)換成 5 進(jìn)制數(shù)為: 0.34414141十進(jìn)制正小數(shù) 0.795000 轉(zhuǎn)換成 6 進(jìn)制數(shù)為: 0.44341530十進(jìn)制正小數(shù) 0.795000 轉(zhuǎn)換成 7 進(jìn)制數(shù)為: 0.53645364十進(jìn)制正小數(shù) 0.795
45、000 轉(zhuǎn)換成 8 進(jìn)制數(shù)為: 0.62702436十進(jìn)制正小數(shù) 0.795000 轉(zhuǎn)換成 9 進(jìn)制數(shù)為: 0.71348853以下代碼提供了這個(gè)功能。其中,dTestNo表示待轉(zhuǎn)的十進(jìn)制小數(shù)。iBase表示進(jìn)制數(shù)。請?zhí)顚懭笔У牟糠帧?void fun(double dTestNo, int iBase){int iT[8];int iNo;printf("十進(jìn)制正小數(shù) %f 轉(zhuǎn)換成 %d 進(jìn)制數(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("十進(jìn)制正小數(shù) %f 轉(zhuǎn)換成 %d 進(jìn)制數(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、;},兩個(gè)作業(yè),地址轉(zhuǎn)換十六進(jìn)制轉(zhuǎn)八進(jìn)制,地址轉(zhuǎn)換2012決賽C高職第3題(19分) 2012決賽Java高職第4題(21分),Excel是最常用的辦公軟件。每個(gè)單元格都有唯一的地址表示。比如:第12行第4列表示為:“D12”,第5行第255列表示為“IU5”。事實(shí)上,Excel提供了兩種地址表示方法,還有一種表示法叫做RC格式地址。 第12行第4列表示為:“R12C4”,第5行第255列表示為“R5C255”。 你的任務(wù)是
51、:編寫程序,實(shí)現(xiàn)從RC地址格式到常規(guī)地址格式的轉(zhuǎn)換?!据斎?、輸出格式要求】 用戶先輸入一個(gè)整數(shù)n(n<100),表示接下來有n行輸入數(shù)據(jù)。 接著輸入的n行數(shù)據(jù)是RC格式的Excel單元格地址表示法。 程序則輸出n行數(shù)據(jù),每行是轉(zhuǎn)換后的常規(guī)地址表示法。 例如:用戶輸入:2R12C4R5C255 則程序應(yīng)該輸出:D12IU5,測試用例與運(yùn)行結(jié)果,,6R1C1R65535C256
52、R100C100R100C99R1C255R255C27,A1IV65535CV100CU100IU1AA255,作業(yè)評測系統(tǒng) BASIC-12:十六進(jìn)制轉(zhuǎn)八進(jìn)制,問題描述 給定n個(gè)十六進(jìn)制正整數(shù),輸出它們對應(yīng)的八進(jìn)制數(shù)。輸入格式 輸入的第一行為一個(gè)正整數(shù)n (1<=n<=10)。 接下來n行,每行一個(gè)由0~9、大寫字母A~F組成的字符串,表示要轉(zhuǎn)換的十六進(jìn)制正整數(shù),每個(gè)十六進(jìn)制數(shù)長度不超過1
53、00000。輸出格式 輸出n行,每行為輸入對應(yīng)的八進(jìn)制正整數(shù)。注意 輸入的十六進(jìn)制數(shù)不會(huì)有前導(dǎo)0,比如012A。 輸出的八進(jìn)制數(shù)也不能有前導(dǎo)0。樣例輸入239123ABC樣例輸出714435274提示 先將十六進(jìn)制數(shù)轉(zhuǎn)換成某進(jìn)制數(shù),再由某進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制。,,因?yàn)橐D(zhuǎn)換的16進(jìn)制整數(shù)太大,所以,不能借助10進(jìn)制轉(zhuǎn)8進(jìn)制。需要借助2進(jìn)制,代碼,32行,[ Add your company sloga
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 05_限制函數(shù)、轉(zhuǎn)換函數(shù)
- 實(shí)訓(xùn)周報(bào)_05_宋盼盼 .xls
- 實(shí)訓(xùn)周報(bào)_05_宋盼盼 .xls
- 05_畢業(yè)論文中期檢查表.doc
- 05_安徽省女職工勞動(dòng)保護(hù)實(shí)施辦法
- 數(shù)論(一)
- 數(shù)論二
- 數(shù)論知識
- 數(shù)論 (3)
- 數(shù)論(二)
- 數(shù)論函數(shù)
- 概數(shù)論
- acm-數(shù)論a
- 初等數(shù)論2
- 數(shù)論問題 (2)
- 初等數(shù)論論文
- noip數(shù)論知識
- 數(shù)論問題 (1)
評論
0/150
提交評論