《C語(yǔ)言程序設(shè)計(jì)》基礎(chǔ)練習(xí)及解析

A+B問(wèn)題（入門(mén)）問(wèn)題描述輸入A、B，輸出A+B。說(shuō)明：在“問(wèn)題描述”這部分，會(huì)給出試題的意思，以及所要求的目標(biāo)。輸入格式輸入的第一行包括兩個(gè)整數(shù)，由空格分隔，分別表示A、B。輸出格式輸出一行，包括一個(gè)整數(shù)，表示A+B的值。樣例輸入1245樣例輸出57數(shù)據(jù)規(guī)模與約定-10000<=A,B<=10000。#include<stdio.h>intmain(){inta,b;scanf("%d%d",&a,&b);printf("%d",a+b);return0;}圓的面積（入門(mén)）問(wèn)題描述給定圓的半徑r，求圓的面積。輸入格式輸入包含一個(gè)整數(shù)r，表示圓的半徑。輸出格式輸出一行，包含一個(gè)實(shí)數(shù)，四舍五入保留小數(shù)點(diǎn)后7位，表示圓的面積。樣例輸入4樣例輸出50.2654825數(shù)據(jù)規(guī)模與約定1<=r<=10000。提示本題對(duì)精度要求較高，請(qǐng)注意π的值應(yīng)該取較精確的值。你可以使用常量來(lái)表示π，比如PI=3.14159265358979323，也可以使用數(shù)學(xué)公式來(lái)求π，比如PI=atan(1.0)*4。#include<stdio.h>#include<math.h>#definePIatan(1.0)*4intmain(){intr;scanf("%d",&r);doubles;s=PI*r*r;printf("%.7f\n",s);return0;}序列求和（大整數(shù)）問(wèn)題描述求1+2+3+...+n的值。輸入格式輸入包括一個(gè)整數(shù)n。輸出格式輸出一行，包括一個(gè)整數(shù)，表示1+2+3+...+n的值。樣例輸入4樣例輸出10樣例輸入100樣例輸出5050數(shù)據(jù)規(guī)模與約定1<=n<=1,000,000,000#include<stdio.h>intmain(){longlongsum=0,n=0;//__int64longlong型scanf("%I64d",&n);sum=(n+1)*n/2;printf("%I64d\n",sum);return0;}閏年判斷（復(fù)雜條件）問(wèn)題描述給定一個(gè)年份，判斷這一年是不是閏年。當(dāng)以下情況之一滿(mǎn)足時(shí)，這一年是閏年：1.年份是4的倍數(shù)而不是100的倍數(shù)；2.年份是400的倍數(shù)。其他的年份都不是閏年。輸入格式輸入包含一個(gè)整數(shù)y，表示當(dāng)前的年份。輸出格式輸出一行，如果給定的年份是閏年，則輸出yes，否則輸出no。樣例輸入2013樣例輸出no樣例輸入2016樣例輸出yes數(shù)據(jù)規(guī)模與約定1990<=y<=2050。#include<stdio.h>usingnamespacestd;intmain(){intyear;while(scanf("%d",&year)!=EOF)if((year%4==0&&year%100!=0)||year%400==0)printf("yes\n");elseprintf("no\n");return0;}Fibonacci數(shù)列（取模）問(wèn)題描述Fibonacci數(shù)列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。當(dāng)n比較大時(shí)，F(xiàn)n也非常大，現(xiàn)在我們想知道，F(xiàn)n除以10007的余數(shù)是多少。輸入格式輸入包含一個(gè)整數(shù)n。輸出格式輸出一行，包含一個(gè)整數(shù)，表示Fn除以10007的余數(shù)。說(shuō)明：在本題中，答案是要求Fn除以10007的余數(shù)，因此我們只要能算出這個(gè)余數(shù)即可，而不需要先計(jì)算出Fn的準(zhǔn)確值，再將計(jì)算的結(jié)果除以10007取余數(shù)，直接計(jì)算余數(shù)往往比先算出原數(shù)再取余簡(jiǎn)單。樣例輸入10樣例輸出55樣例輸入22樣例輸出7704數(shù)據(jù)規(guī)模與約定1<=n<=1,000,000。#include<stdlib.h>#include<stdio.h>#defineMAXN1000001intn,i,F[MAXN];intmain(){scanf("%d",&n);F[1]=1;F[2]=1;for(i=3;i<=n;++i)F[i]=(F[i-1]+F[i-2])%10007;printf("%d\n",F[n]);return0;}01字串（取模）問(wèn)題描述對(duì)于長(zhǎng)度為5位的一個(gè)01串，每一位都可能是0或1，一共有32種可能。它們的前幾個(gè)是：0000000001000100001100100請(qǐng)按從小到大的順序輸出這32種01串。輸出格式輸出32行，按從小到大的順序每行一個(gè)長(zhǎng)度為5的01串。樣例輸出00000000010001000011<以下部分省略>#include<stdio.h>intmain(){inti; for(i=0;i<32;i++){ printf("%d",i%32/16); printf("%d",i%16/8); printf("%d",i%8/4); printf("%d",i%4/2); printf("%d\n",i%2); }return0;}特殊的數(shù)字（取模）問(wèn)題描述153是一個(gè)非常特殊的數(shù)，它等于它的每位數(shù)字的立方和，即153=1*1*1+5*5*5+3*3*3。編程求所有滿(mǎn)足這種條件的三位十進(jìn)制數(shù)。輸出格式按從小到大的順序輸出滿(mǎn)足條件的三位十進(jìn)制數(shù)，每個(gè)數(shù)占一行。#include<iostream>#include<cmath>usingnamespacestd;intmain(){ inti,a,b,c; for(i=100;i<1000;i++){ a=i/100; //百位 b=(i%100)/10; //十位 c=i%10; //個(gè)位 if(i==pow(a,3)+pow(b,3)+pow(c,3)) cout<<i<<endl; } return0;}特殊回文數(shù)（取模，技巧）

問(wèn)題描述123321是一個(gè)非常特殊的數(shù)，它從左邊讀和從右邊讀是一樣的。輸入一個(gè)正整數(shù)n，編程求所有這樣的五位和六位十進(jìn)制數(shù)，滿(mǎn)足各位數(shù)字之和等于n。輸入格式輸入一行，包含一個(gè)正整數(shù)n。輸出格式按從小到大的順序輸出滿(mǎn)足條件的整數(shù)，每個(gè)整數(shù)占一行。樣例輸入52樣例輸出899998989989998899數(shù)據(jù)規(guī)模和約定1<=n<=54。#include<stdio.h>intmain(){ intn,x,f,tmp,i,j;scanf("%d",&n);for(f=0,x=10000,i=x+1;i<1000000;i++){if(i>99999)x=100000;if(i%10!=i/x%10||i/10%10!=i*10/x%10||i/100%10!=i*100/x%10)continue;//循環(huán)判斷前后的數(shù)字是否一致for(tmp=0,j=i;j;tmp+=j%10,j/=10);//第2項(xiàng)等價(jià)于j!=0if(n==tmp){printf("%d\n",i);f=1;}}return0;}字母圖形（數(shù)組，技巧）

問(wèn)題描述利用字母可以組成一些美麗的圖形，下面給出了一個(gè)例子：ABCDEFGBABCDEFCBABCDEDCBABCDEDCBABC這是一個(gè)5行7列的圖形，請(qǐng)找出這個(gè)圖形的規(guī)律，并輸出一個(gè)n行m列的圖形。輸入格式輸入一行，包含兩個(gè)整數(shù)n和m，分別表示你要輸出的圖形的行數(shù)的列數(shù)。輸出格式輸出n行，每個(gè)m個(gè)字符，為你的圖形。樣例輸入57樣例輸出ABCDEFGBABCDEFCBABCDEDCBABCDEDCBABC數(shù)據(jù)規(guī)模與約定1<=n,m<=26。#include<iostream>#include<cmath>usingnamespacestd;intmain(){chara[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";intn,m;cin>>n>>m;for(inti=0;i<n;i++){for(intj=0;j<m;j++)cout<<a[abs(i-j)];cout<<endl;}return0;}數(shù)列特征（數(shù)組，技巧）問(wèn)題描述給出n個(gè)數(shù)，找出這n個(gè)數(shù)的最大值，最小值，和。輸入格式第一行為整數(shù)n，表示數(shù)的個(gè)數(shù)。第二行有n個(gè)數(shù)，為給定的n個(gè)數(shù)，每個(gè)數(shù)的絕對(duì)值都小于10000。輸出格式輸出三行，每行一個(gè)整數(shù)。第一行表示這些數(shù)中的最大值，第二行表示這些數(shù)中的最小值，第三行表示這些數(shù)的和。樣例輸入513-245樣例輸出5-211數(shù)據(jù)規(guī)模與約定1<=n<=10000。#include<iostream>usingnamespacestd;intmain(){ intn,i,maxv=-10001,minv=10001,sum=0;//這一行數(shù)據(jù)很重要 inta[10000]; cin>>n; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++){ maxv=max(maxv,a[i]); minv=min(minv,a[i]); sum+=a[i]; } cout<<maxv<<endl<<minv<<endl<<sum<<endl; return0;}查找整數(shù)（數(shù)組）問(wèn)題描述給出一個(gè)包含n個(gè)整數(shù)的數(shù)列，問(wèn)整數(shù)a在數(shù)列中的第一次出現(xiàn)是第幾個(gè)。輸入格式第一行包含一個(gè)整數(shù)n。第二行包含n個(gè)非負(fù)整數(shù)，為給定的數(shù)列，數(shù)列中的每個(gè)數(shù)都不大于10000。第三行包含一個(gè)整數(shù)a，為待查找的數(shù)。輸出格式如果a在數(shù)列中出現(xiàn)了，輸出它第一次出現(xiàn)的位置(位置從1開(kāi)始編號(hào))，否則輸出-1。樣例輸入61948399樣例輸出2數(shù)據(jù)規(guī)模與約定1<=n<=1000。#include<stdio.h>intmain(){intn=0,a=0,i=0;intnNum[1000];scanf("%d",&n);for(i=0;i<n;++i)scanf("%d",&nNum[i]);scanf("%d",&a);for(i=0;i<n;++i)if(nNum[i]==a){//找到相等printf("%d\n",i+1);return0;//退出}}printf("-1\n");return0;}楊輝三角形（二維數(shù)組，技巧）問(wèn)題描述楊輝三角形又稱(chēng)Pascal三角形，它的第i+1行是(a+b)i的展開(kāi)式的系數(shù)。它的一個(gè)重要性質(zhì)是：三角形中的每個(gè)數(shù)字等于它兩肩上的數(shù)字相加。下面給出了楊輝三角形的前4行：

1

11

1211331給出n，輸出它的前n行。輸入格式輸入包含一個(gè)數(shù)n。輸出格式輸出楊輝三角形的前n行。每一行從這一行的第一個(gè)數(shù)開(kāi)始依次輸出，中間使用一個(gè)空格分隔。請(qǐng)不要在前面輸出多余的空格。樣例輸入4樣例輸出1111211331數(shù)據(jù)規(guī)模與約定1<=n<=34。#include<iostream>usingnamespacestd;intmain(){intn,yh[34][34],i,j;cin>>n;for(i=0;i<n;i++){yh[i][0]=1;yh[i][i]=1;for(j=1;j<i;j++)yh[i][j]=yh[i-1][j-1]+yh[i-1][j];}for(i=0;i<n;i++){for(j=0;j<=i;j++){cout<<yh[i][j];if(j<i)cout<<'';}cout<<endl;}return0;}回文數(shù)（技巧）

問(wèn)題描述1221是一個(gè)非常特殊的數(shù)，它從左邊讀和從右邊讀是一樣的，編程求所有這樣的四位十進(jìn)制數(shù)。輸出格式按從小到大的順序輸出滿(mǎn)足條件的四位十進(jìn)制數(shù)。#include<stdio.h>intmain(){inti,j;inta,b;for(i=1;i<=9;i++)for(j=0;j<=9;j++)printf("%d\n",i*1000+j*100+j*10+i);return0;}時(shí)間轉(zhuǎn)換（技巧）問(wèn)題描述給定一個(gè)以秒為單位的時(shí)間t，要求用“<H>:<M>:<S>”的格式來(lái)表示這個(gè)時(shí)間。<H>表示時(shí)間，<M>表示分鐘，而<S>表示秒，它們都是整數(shù)且沒(méi)有前導(dǎo)的“0”。例如，若t=0，則應(yīng)輸出是“0:0:0”；若t=3661，則輸出“1:1:1”。輸入格式輸入只有一行，是一個(gè)整數(shù)t（0<=t<=86399）。輸出格式輸出只有一行，是以“<H>:<M>:<S>”的格式所表示的時(shí)間，不包括引號(hào)。樣例輸入0樣例輸出0:0:0樣例輸入5436樣例輸出1:30:36#include<stdio.h>intmain(){intn,a=0,b=0,c=0;scanf("%d",&n);if(n>=3600){a=n/3600;n=n-a*3600;}b=n/60;n-=b*60;c=n;printf("%d:%d:%d",a,b,c);return0;}十進(jìn)制轉(zhuǎn)十六進(jìn)制（數(shù)組，技巧）問(wèn)題描述十六進(jìn)制數(shù)是在程序設(shè)計(jì)時(shí)經(jīng)常要使用到的一種整數(shù)的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16個(gè)符號(hào)，分別表示十進(jìn)制數(shù)的0至15。十六進(jìn)制的計(jì)數(shù)方法是滿(mǎn)16進(jìn)1，所以十進(jìn)制數(shù)16在十六進(jìn)制中是10，而十進(jìn)制的17在十六進(jìn)制中是11，以此類(lèi)推，十進(jìn)制的30在十六進(jìn)制中是1E。給出一個(gè)非負(fù)整數(shù)，將它表示成十六進(jìn)制的形式。輸入格式輸入包含一個(gè)非負(fù)整數(shù)a，表示要轉(zhuǎn)換的數(shù)。0<=a<=2147483647輸出格式輸出這個(gè)整數(shù)的16進(jìn)制表示樣例輸入30樣例輸出1E#include"stdio.h"intmain(){chara[10];inti=0;intn,temp;scanf("%d",&n);if(n==0)//注意題目要求的n是非負(fù)數(shù)，要考慮n=0時(shí)的情況printf("0\n");while(n>0){temp=n%16;if(temp>=10)a[i++]='A'+temp-10;elsea[i++]=temp+'0';n/=16;} for(intj=i-1;j>=0;j--) printf("%c",a[j]); return0;}十六進(jìn)制轉(zhuǎn)十進(jìn)制（數(shù)組，技巧）問(wèn)題描述從鍵盤(pán)輸入一個(gè)不超過(guò)8位的正的十六進(jìn)制數(shù)字符串，將它轉(zhuǎn)換為正的十進(jìn)制數(shù)后輸出。注：十六進(jìn)制數(shù)中的10~15分別用大寫(xiě)的英文字母A、B、C、D、E、F表示。樣例輸入FFFF樣例輸出65535#include<iostream>#include<cmath>#include<cstring>usingnamespacestd;intmain(){chars[10000];cin>>s;intlen=strlen(s);longlongintans=0;for(inti=0;i<len;i++){if(s[i]>='A'&&s[i]<='Z')s[i]=int(s[i]-'A')+10+'0';ans+=((s[i]-'0')*(pow(16,len-1-i)));}printf("%I64d\n",ans);return0;}芯片測(cè)試（數(shù)組，技巧）問(wèn)題描述有n（2≤n≤20）塊芯片，有好有壞，已知好芯片比壞芯片多。每個(gè)芯片都能用來(lái)測(cè)試其他芯片。用好芯片測(cè)試其他芯片時(shí)，能正確給出被測(cè)試芯片是好還是壞。而用壞芯片測(cè)試其他芯片時(shí)，會(huì)隨機(jī)給出好或是壞的測(cè)試結(jié)果（即此結(jié)果與被測(cè)試芯片實(shí)際的好壞無(wú)關(guān)）。給出所有芯片的測(cè)試結(jié)果，問(wèn)哪些芯片是好芯片。輸入格式輸入數(shù)據(jù)第一行為一個(gè)整數(shù)n，表示芯片個(gè)數(shù)。第二行到第n+1行為n*n的一張表，每行n個(gè)數(shù)據(jù)。表中的每個(gè)數(shù)據(jù)為0或1，在這n行中的第i行第j列（1≤i,j≤n）的數(shù)據(jù)表示用第i塊芯片測(cè)試第j塊芯片時(shí)得到的測(cè)試結(jié)果，1表示好，0表示壞，i=j時(shí)一律為1（并不表示該芯片對(duì)本身的測(cè)試結(jié)果。芯片不能對(duì)本身進(jìn)行測(cè)試）。輸出格式按從小到大的順序輸出所有好芯片的編號(hào)樣例輸入3101010101樣例輸出13分析：因?yàn)槌^(guò)半數(shù)的芯片是好的，所以這些芯片對(duì)于其他芯片的測(cè)試結(jié)果是正確的。所以假設(shè)該芯片是好芯片，它除了它自身測(cè)試自身之外的其他測(cè)試結(jié)果為好的個(gè)數(shù)將超過(guò)一半。同理，假設(shè)該芯片是壞芯片，他將有超過(guò)半數(shù)的測(cè)試結(jié)果是壞芯片。所以只要根據(jù)每一列的所有測(cè)試結(jié)果，判斷其為好芯片的總數(shù)>=n/2的時(shí)候，這個(gè)芯片就是好芯片。#include<iostream>usingnamespacestd;intmain(){ inti,j,n,a[20][20]; cin>>n; for(i=0;i<n;i++) for(j=0;j<n;j++) cin>>a[i][j]; for(i=0;i<n;i++){ intcnt=0; for(j=0;j<n;j++) if(i!=j) cnt+=a[j][i]; if(cnt>=n/2) cout<<i+1<<""; } return0;}回形取數(shù)（二維數(shù)組，技巧）問(wèn)題描述回形取數(shù)就是沿矩陣的邊取數(shù)，若當(dāng)前方向上無(wú)數(shù)可取或已經(jīng)取過(guò)，則左轉(zhuǎn)90度。一開(kāi)始位于矩陣左上角，方向向下。輸入格式輸入第一行是兩個(gè)不超過(guò)200的正整數(shù)m,n，表示矩陣的行和列。接下來(lái)m行每行n個(gè)整數(shù)，表示這個(gè)矩陣。輸出格式輸出只有一行，共mn個(gè)數(shù)，為輸入矩陣回形取數(shù)得到的結(jié)果。數(shù)之間用一個(gè)空格分隔，行末不要有多余的空格。樣例輸入33123456789樣例輸出147896325樣例輸入32123456樣例輸出135642#include<iostream>#include<cstring>usingnamespacestd;intmain(){intm,n; inta[202][202];inti,j; cin>>m>>n;for(i=0;i<m;i++)for(j=0;j<n;j++)cin>>a[i][j];intsum=m*n;i=-1;j=0;while(sum){ //向下走 while(a[++i][j]!=-1&&i<m){ cout<<a[i][j]<<""; a[i][j]=-1; sum--; } i--;//修正行坐標(biāo) //向右走 while(a[i][++j]!=-1&&j<n){ cout<<a[i][j]<<""; a[i][j]=-1; sum--; } j--;//修正列坐標(biāo) //向上走 while(a[--i][j]!=-1&&i>=0){ cout<<a[i][j]<<""; a[i][j]=-1; sum--; } i++; //向左走 while(a[i][--j]!=-1&&j>=0){ cout<<a[i][j]<<""; a[i][j]=-1; sum--; } j++;}return0;}報(bào)時(shí)助手（字符數(shù)組，技巧）問(wèn)題描述給定當(dāng)前的時(shí)間，請(qǐng)用英文的讀法將它讀出來(lái)。時(shí)間用時(shí)h和分m表示，在英文的讀法中，讀一個(gè)時(shí)間的方法是：如果m為0，則將時(shí)讀出來(lái)，然后加上“o'clock”，如3:00讀作“threeo'clock”。如果m不為0，則將時(shí)讀出來(lái)，然后將分讀出來(lái)，如5:30讀作“fivethirty”。時(shí)和分的讀法使用的是英文數(shù)字的讀法，其中0~20讀作：0:zero,1:one,2:two,3:three,4:four,5:five,6:six,7:seven,8:eight,9:nine,10:ten,11:eleven,12:twelve,13:thirteen,14:fourteen,15:fifteen,16:sixteen,17:seventeen,18:eighteen,19:nineteen,20:twenty。30讀作thirty，40讀作forty，50讀作fifty。對(duì)于大于20小于60的數(shù)字，首先讀整十的數(shù)，然后再加上個(gè)位數(shù)。如31首先讀30再加1的讀法，讀作“thirtyone”。按上面的規(guī)則21:54讀作“twentyonefiftyfour”，9:07讀作“nineseven”，0:15讀作“zerofifteen”。輸入格式輸入包含兩個(gè)非負(fù)整數(shù)h和m，表示時(shí)間的時(shí)和分。非零的數(shù)字前沒(méi)有前導(dǎo)0。h小于24，m小于60。輸出格式輸出時(shí)間時(shí)刻的英文。樣例輸入015樣例輸出zerofifteen#include<iostream>#include<string>usingnamespacestd;stringn[100]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty","thirty","forty","fifty"};voidass(intnum){inta=num/10;intb=num%10;if(num<=20)cout<<n[num];else{cout<<n[a+18];if(b!=0)cout<<""<<n[b];}}voidtime_ass(inthour,intminu){if(minu==0){ass(hour);cout<<"o'clock"<<endl;}else{ass(hour);cout<<"";ass(minu);cout<<endl;}}intmain(){inth,m;cin>>h>>m;time_ass(h,m);return0;}Huffuman樹(shù)（排序，技巧）

問(wèn)題描述Huffman樹(shù)在編碼中有著廣泛的應(yīng)用。在這里，我們只關(guān)心Huffman樹(shù)的構(gòu)造過(guò)程。給出一列數(shù){pi}={p0,p1,…,pn-1}，用這列數(shù)構(gòu)造Huffman樹(shù)的過(guò)程如下：1.找到{pi}中最小的兩個(gè)數(shù)，設(shè)為pa和pb，將pa和pb從{pi}中刪除掉，然后將它們的和加入到{pi}中。這個(gè)過(guò)程的費(fèi)用記為pa

+pb。2.重復(fù)步驟1，直到{pi}中只剩下一個(gè)數(shù)。在上面的操作過(guò)程中，把所有的費(fèi)用相加，就得到了構(gòu)造Huffman樹(shù)的總費(fèi)用。本題任務(wù)：對(duì)于給定的一個(gè)數(shù)列，現(xiàn)在請(qǐng)你求出用該數(shù)列構(gòu)造Huffman樹(shù)的總費(fèi)用。例如，對(duì)于數(shù)列{pi}={5,3,8,2,9}，Huffman樹(shù)的構(gòu)造過(guò)程如下：1.找到{5,3,8,2,9}中最小的兩個(gè)數(shù)，分別是2和3，從{pi}中刪除它們并將和5加入，得到{5,8,9,5}，費(fèi)用為5。2.找到{5,8,9,5}中最小的兩個(gè)數(shù)，分別是5和5，從{pi}中刪除它們并將和10加入，得到{8,9,10}，費(fèi)用為10。3.找到{8,9,10}中最小的兩個(gè)數(shù)，分別是8和9，從{pi}中刪除它們并將和17加入，得到{10,17}，費(fèi)用為17。4.找到{10,17}中最小的兩個(gè)數(shù)，分別是10和17，從{pi}中刪除它們并將和27加入，得到{27}，費(fèi)用為27。5.現(xiàn)在，數(shù)列中只剩下一個(gè)數(shù)27，構(gòu)造過(guò)程結(jié)束，總費(fèi)用為5+10+17+27=59。輸入格式輸入的第一行包含一個(gè)正整數(shù)n（n<=100）。接下來(lái)是n個(gè)正整數(shù)，表示p0,p1,…,pn-1，每個(gè)數(shù)不超過(guò)1000。輸出格式輸出用這些數(shù)構(gòu)造Huffman樹(shù)的總費(fèi)用。樣例輸入553829樣例輸出59#include<iostream>#include<algorithm>usingnamespacestd;intmain(){intn; inta[100];cin>>n;longsum=0;inti,j=0,t=n;for(i=0;i<n;i++) cin>>a[i];while(j<n-1){ sort(a+j,a+n); //排序 sum+=(a[j]+a[j+1]); //費(fèi)用 a[j+1]+=a[j]; //用最小兩項(xiàng)的和覆蓋第2較小值 j++; //指針移動(dòng)到下一個(gè)數(shù)字 }cout<<sum<<endl; return0;}高精度加法（字符數(shù)組，技巧）問(wèn)題描述輸入兩個(gè)整數(shù)a和b，輸出這兩個(gè)整數(shù)的和。a和b都不超過(guò)100位。算法描述由于a和b都比較大，所以不能直接使用語(yǔ)言中的標(biāo)準(zhǔn)數(shù)據(jù)類(lèi)型來(lái)存儲(chǔ)。對(duì)于這種問(wèn)題，一般使用數(shù)組來(lái)處理。定義一個(gè)數(shù)組A，A[0]用于存儲(chǔ)a的個(gè)位，A[1]用于存儲(chǔ)a的十位，依此類(lèi)推。同樣可以用一個(gè)數(shù)組B來(lái)存儲(chǔ)b。計(jì)算c=a+b的時(shí)候，首先將A[0]與B[0]相加，如果有進(jìn)位產(chǎn)生，則把進(jìn)位（即和的十位數(shù)）存入r，把和的個(gè)位數(shù)存入C[0]，即C[0]等于(A[0]+B[0])%10。然后計(jì)算A[1]與B[1]相加，這時(shí)還應(yīng)將低位進(jìn)上來(lái)的值r也加起來(lái)，即C[1]應(yīng)該是A[1]、B[1]和r三個(gè)數(shù)的和．如果又有進(jìn)位產(chǎn)生，則仍可將新的進(jìn)位存入到r中，和的個(gè)位存到C[1]中。依此類(lèi)推，即可求出C的所有位。最后將C輸出即可。輸入格式輸入包括兩行，第一行為一個(gè)非負(fù)整數(shù)a，第二行為一個(gè)非負(fù)整數(shù)b。兩個(gè)整數(shù)都不超過(guò)100位，兩數(shù)的最高位都不是0。輸出格式輸出一行，表示a+b的值。樣例輸入201001222010012212345678902010012220100122樣例輸出20100122203011233454668012#include<iostream>#include<string.h>usingnamespacestd;intmain(){chara[1111],b[1111];intc[1111];cin>>a>>b;inti,j,k=0;intr=0;for(i=strlen(a)-1,j=strlen(b)-1;i>=0&&j>=0;i--,j--){intp=(a[i]-'0')+(b[j]-'0')+r;r=p/10; //進(jìn)位c[k++]=p%10;//余數(shù)加到數(shù)組中}while(i>=0){//如果a較大intp=(a[i]-'0')+r;r=p/10;c[k++]=p%10;i--;}while(j>=0){//如果b較大intp=(b[j]-'0')+r;r=p/10;c[k++]=p%10;j--;}if(r){//判斷最高位有沒(méi)有進(jìn)位c[k++]=r;}for(i=k-1;i>=0;i--){//輸出最后結(jié)果cout<<c[i];}return0;}高精度乘法（字符數(shù)組，技巧）#include<stdio.h>#include<string.h>intmain(){charm[555],n[555],temp[555];inti,j,len_m,len_n;inta[555]={0},b[555]={0},c[1111]={0};scanf("%s",m);scanf("%s",n); len_m=strlen(m); len_n=strlen(n); //確保第一個(gè)數(shù)較大if(len_m<len_n){strcpy(temp,m);strcpy(m,n);strcpy(n,temp);}//分離數(shù)字位for(i=0;i<=len_m-1;i++)a[i]=m[len_m-1-i]-'0';for(i=0;i<=len_n-1;i++)b[i]=n[len_n-1-i]-'0';//用第2個(gè)數(shù)的每一位乘以第1個(gè)數(shù)的每一位for(i=0;i<len_n;i++)for(j=0;j<len_m;j++)c[i+j]+=a[j]*b[i]; //處理進(jìn)位for(i=0;i<2*len_m;i++)if(c[i]>=10){c[i+1]+=c[i]/10;c[i]%=10;}i=2*len_m;while(!c[i])i--; //跳過(guò)前導(dǎo)0if(i<0)printf("0");elsefor(;i>=0;i--)printf("%d",c[i]);return0;}階乘計(jì)算（數(shù)組，技巧）問(wèn)題描述輸入一個(gè)正整數(shù)n，輸出n!的值。其中n!=1*2*3*…*n。算法描述n!可能很大，而計(jì)算機(jī)能表示的整數(shù)范圍有限，需要使用高精度計(jì)算的方法。使用一個(gè)數(shù)組A來(lái)表示一個(gè)大整數(shù)a，A[0]表示a的個(gè)位，A[1]表示a的十位，依次類(lèi)推。將a乘以一個(gè)整數(shù)k變?yōu)閷?shù)組A的每一個(gè)元素都乘以k，請(qǐng)注意處理相應(yīng)的進(jìn)位。首先將a設(shè)為1，然后乘2，乘3，當(dāng)乘到n時(shí)，即得到了n!的值。輸入格式輸入包含一個(gè)正整數(shù)n，n<=1000。輸出格式輸出n!的準(zhǔn)確值。樣例輸入10樣例輸出3628800#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX4000intmain(){intn,a[MAX],i,j,s,r=0;scanf("%d",&n);memset(a,0,sizeof(a));//全部設(shè)置為0a[0]=1;for(i=2;i<=n;i++){for(j=0;j<MAX;j++){s=a[j]*i+r;r=s/10; //進(jìn)位a[j]=s%10; //當(dāng)前位}}for(i=MAX-1;i>=0;i--){if(a[i])//遇到第1個(gè)非0數(shù)字退出break;}for(j=i;j>=0;j--)//倒序輸出printf("%d",a[j]);return0;}數(shù)的讀法（數(shù)組）問(wèn)題描述Tom教授正在給研究生講授一門(mén)關(guān)于基因的課程，有一件事情讓他頗為頭疼：一條染色體上有成千上萬(wàn)個(gè)堿基對(duì)，它們從0開(kāi)始編號(hào)，到幾百萬(wàn)，幾千萬(wàn)，甚至上億。比如說(shuō)，在對(duì)學(xué)生講解第1234567009號(hào)位置上的堿基時(shí)，光看著數(shù)字是很難準(zhǔn)確的念出來(lái)的。所以，他迫切地需要一個(gè)系統(tǒng)，然后當(dāng)他輸入1234567009時(shí)，會(huì)給出相應(yīng)的念法：十二億三千四百五十六萬(wàn)七千零九用漢語(yǔ)拼音表示為shieryisanqiansibaiwushiliuwanqiqianlingjiu這樣他只需要照著念就可以了。你的任務(wù)是幫他設(shè)計(jì)這樣一個(gè)系統(tǒng)：給定一個(gè)阿拉伯?dāng)?shù)字串，你幫他按照中文讀寫(xiě)的規(guī)范轉(zhuǎn)為漢語(yǔ)拼音字串，相鄰的兩個(gè)音節(jié)用一個(gè)空格符格開(kāi)。注意必須嚴(yán)格按照規(guī)范，比如說(shuō)“10010”讀作“yiwanlingyishi”而不是“yiwanlingshi”，“100000”讀作“shiwan”而不是“yishiwan”，“2000”讀作“erqian”而不是“l(fā)iangqian”。輸入格式有一個(gè)數(shù)字串，數(shù)值大小不超過(guò)2,000,000,000。輸出格式是一個(gè)由小寫(xiě)英文字母，逗號(hào)和空格組成的字符串，表示該數(shù)的英文讀法。樣例輸入1234567009樣例輸出shieryisanqiansibaiwushiliuwanqiqianlingjiu#include<iostream>usingnamespacestd;intmain(){char*num[]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};char*wei[]={"shi","bai","qian","wan","yi"};char*str[20];//存最后結(jié)果inti,j,k,n,l[2]={0};i=0;//4位數(shù)為一組 j=0;//數(shù)組str的下標(biāo)cin>>n;while(n>0){k=n%10;//n的最后一位數(shù)n/=10;if(k>0){if(i>0){if(i>=4&&!l[i/4-1]){//如果是大于等于4位數(shù)的數(shù)，且已經(jīng)加了一個(gè)wei，那么就不要添加l[i/4-1]=1;str[j++]=wei[i/4+2];}if(i%4!=0){str[j++]=wei[i%4-1];}}str[j++]=num[k];}elseif(j>0&&str[j-1]!=num[0]){//判斷連續(xù)另個(gè)是不是都是0str[j++]=num[0];}i++;}if(!(str[j-1]=="yi"&&j>1&&str[j-2]=="shi"))//去除yishi的情況cout<<str[j-1]<<"";//輸出第一位數(shù)for(i=j-2;i>=0;i--){//輸出剩余的各個(gè)字符串cout<<str[i]<<"";}return0;}矩陣乘法（二維數(shù)組）問(wèn)題描述給定一個(gè)N階矩陣A，輸出A的M次冪（M是非負(fù)整數(shù)）例如：A=1234A的2次冪7101522輸入格式第一行是一個(gè)正整數(shù)N、M（1<=N<=30,0<=M<=5），表示矩陣A的階數(shù)和要求的冪數(shù)接下來(lái)N行，每行N個(gè)不超過(guò)10的非負(fù)整數(shù)，描述矩陣A的值輸出格式輸出共N行，每行N個(gè)整數(shù)，表示A的M次冪所對(duì)應(yīng)的矩陣。相鄰的數(shù)之間用一個(gè)空格隔開(kāi)樣例輸入221234樣例輸出7101522#include<iostream>usingnamespacestd;//輸出矩陣voidprint(intc[][101],intn){ inti,j;for(i=0;i<n;i++){for(j=0;j<n;j++){cout<<c[i][j]<<"";}cout<<endl;}}//矩陣乘法voidmatrix(inta[][101],intb[][101],intc[][101],intn,intm){ intp,i,j,k,t;for(p=1;p<m;p++){for(i=0;i<n;i++){for(j=0;j<n;j++){t=0;for(k=0;k<n;k++){t+=a[i][k]*b[k][j];c[i][j]=t;}}}for(i=0;i<n;i++){for(j=0;j<n;j++){b[i][j]=c[i][j];}}}}intmain(){intn,m,i,j;inta[101][101]={0},b[101][101]={0},c[101][101]={0};cin>>n>>m;for(i=0;i<n;i++)for(j=0;j<n;j++) {cin>>a[i][j]; b[i][j]=a[i][j];}if(!m){for(i=0;i<n;i++)for(j=0;j<n;j++)if(i==j)c[i][j]=1;print(c,n);}elseif(m==1)print(a,n);else{matrix(a,b,c,n,m);print(c,n);}return0;}十六進(jìn)制轉(zhuǎn)八進(jìn)制（數(shù)組）問(wèn)題描述給定n個(gè)十六進(jìn)制正整數(shù)，輸出它們對(duì)應(yīng)的八進(jìn)制數(shù)。輸入格式輸入的第一行為一個(gè)正整數(shù)n（1<=n<=10）。接下來(lái)n行，每行一個(gè)由0~9、大寫(xiě)字母A~F組成的字符串，表示要轉(zhuǎn)換的十六進(jìn)制正整數(shù)，每個(gè)十六進(jìn)制數(shù)長(zhǎng)度不超過(guò)100000。輸出格式輸出n行，每行為輸入對(duì)應(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)制。#include<iostream>#include<string>usingnamespacestd;intmain(){intn=0,i=0,j=0,temp=0,nNum=0;charch;stringstrHex[10];stringstrBin[10];stringstrOct[10];cin>>n;for(i=0;i<n;++i)cin>>strHex[i];//十六進(jìn)制轉(zhuǎn)二進(jìn)制for(i=0;i<n;++i){j=0;while(strHex[i][j]){switch(strHex[i][j]){case'0':strBin[i]+="0000";break;case'1':strBin[i]+="0001";break;case'2':strBin[i]+="0010";break;case'3':strBin[i]+="0011";break;case'4':strBin[i]+="0100";break;case'5':strBin[i]+="0101";break;case'6':strBin[i]+="0110";break;case'7':strBin[i]+="0111";break;case'8':strBin[i]+="1000";break;case'9':strBin[i]+="1001";break;case'A':strBin[i]+="1010";break;case'B':strBin[i]+="1011";break;case'C':strBin[i]+="1100";break;case'D':strBin[i]+="1101";break;case'E':strBin[i]+="1110";break;case'F':strBin[i]+="1111";break;default:break;}++j;}}//二進(jìn)制轉(zhuǎn)化為八進(jìn)制for(i=0;i<n;++i){j=strBin[i].size()-1;//獲得長(zhǎng)度while(strBin[i][j]&&j>=0){temp=3;nNum=0;while(temp--&&j>=0){if('1'==strBin[i][j]){switch(temp){case0:nNum+=4;break;case1:nNum+=2;break;case2:nNum+=1;break;default:break;}}--j;}strOct[i]+=(nNum+'0');}}//字符串逆序for(i=0;i<n;++i){temp=strOct[i].size()-1;for(j=0;j<=temp/2;++j){ch=strOct[i][j];strOct[i][j]=strOct[i][temp-j];strOct[i][temp-j]=ch;}}//打印for(i=0;i<n;++i){j=0;while(strOct[i][j++]=='0');//跳過(guò)前面的0for(--j;j<strOct[i].size();++j)cout<<strOct[i][j]-'0';cout<<endl;}return0;}數(shù)列排序（系統(tǒng)函數(shù)）問(wèn)題描述給定一個(gè)長(zhǎng)度為n的數(shù)列，將這個(gè)數(shù)列按從小到大的順序排列。1<=n<=200輸入格式第一行為一個(gè)整數(shù)n。第二行包含n個(gè)整數(shù)，為待排序的數(shù)，每個(gè)整數(shù)的絕對(duì)值小于10000。輸出格式輸出一行，按從小到大的順序輸出排序后的數(shù)列。樣例輸入583649樣例輸出34689#include<stdio.h>#include<algorithm>usingnamespacestd;intmain(){intn,a[200+5];scanf("%d",&n);for(inti=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);for(i=0;i<n;i++)printf("%d",a[i]);printf("\n"); return0;}字符串對(duì)比（系統(tǒng)函數(shù)）問(wèn)題描述給定兩個(gè)僅由大寫(xiě)字母或小寫(xiě)字母組成的字符串(長(zhǎng)度介于1到10之間)，它們之間的關(guān)系是以下4中情況之一：1：兩個(gè)字符串長(zhǎng)度不等。比如Beijing和Hebei2：兩個(gè)字符串不僅長(zhǎng)度相等，而且相應(yīng)位置上的字符完全一致(區(qū)分大小寫(xiě))，比如Beijing和Beijing3：兩個(gè)字符串長(zhǎng)度相等，相應(yīng)位置上的字符僅在不區(qū)分大小寫(xiě)的前提下才能達(dá)到完全一致（也就是說(shuō)，它并不滿(mǎn)足情況2）。比如beijing和BEIjing4：兩個(gè)字符串長(zhǎng)度相等，但是即使是不區(qū)分大小寫(xiě)也不能使這兩個(gè)字符串一致。比如Beijing和Nanjing編程判斷輸入的兩個(gè)字符串之間的關(guān)系屬于這四類(lèi)中的哪一類(lèi)，給出所屬的類(lèi)的編號(hào)。輸入格式包括兩行，每行都是一個(gè)字符串輸出格式僅有一個(gè)數(shù)字，表明這兩個(gè)字符串的關(guān)系編號(hào)樣例輸入BEIjingbeiJing樣例輸出3#include<iostream>#include<cstring>usingnamespacestd;intmain(){charstr1[11],str2[11];cin>>str1;cin>>str2;if(strlen(str1)!=strlen(str2))cout<<"1";else{if(!strcmp(str1,str2))cout<<"2";elseif(!strcmpi(str1,str2))cout<<"3";elsecout<<"4";}cout<<endl;return0;}矩形面積交（排序，技巧）問(wèn)題描述平面上有兩個(gè)矩形，它們的邊平行于直角坐標(biāo)系的X軸或Y軸。對(duì)于每個(gè)矩形，我們給出它的一對(duì)相對(duì)頂點(diǎn)的坐標(biāo)，請(qǐng)你編程算出兩個(gè)矩形的交的面積。輸入格式輸入僅包含兩行，每行描述一個(gè)矩形。在每行中，給出矩形的一對(duì)相對(duì)頂點(diǎn)的坐標(biāo)，每個(gè)點(diǎn)的坐標(biāo)都用兩個(gè)絕對(duì)值不超過(guò)10^7的實(shí)數(shù)表示。輸出格式輸出僅包含一個(gè)實(shí)數(shù)，為交的面積，保留到小數(shù)后兩位。樣例輸入11332244樣例輸出1.00#include<cstdio>#include<algorithm>usingnamespacestd;intmain(){doublex[4];doubley[4]; inti;for(i=0;i<4;i++) scanf("%lf%lf",&x[i],&y[i]); //由于輸入的點(diǎn)可能是矩形的主對(duì)角線的兩個(gè)頂點(diǎn)，也可能是副對(duì)角線的兩個(gè)頂點(diǎn)，所以對(duì)坐標(biāo)進(jìn)行排序，統(tǒng)一成矩形的主對(duì)角線上的兩個(gè)頂點(diǎn)，方便判斷相離。sort(x,x+2);sort(x+2,x+4);sort(y,y+2);sort(y+2,y+4); //判斷相離的四種方式，即以第一個(gè)矩形為中心，另一個(gè)矩形在其四周的相離方式。if(x[1]<=x[2]||x[0]>=x[3]||y[0]>=y[3]||y[1]<=y[2]) printf("%.2lf\n",0);else{ //對(duì)輸入的四個(gè)點(diǎn)的橫坐標(biāo)與縱坐標(biāo)分別進(jìn)行升序排序sort(x,x+4);sort(y,y+4);printf("%.2lf\n",(x[2]-x[1])*(y[2]-y[1]));}return0;}分解質(zhì)因數(shù)（遞歸，技巧）問(wèn)題描述求出區(qū)間[a,b]中所有整數(shù)的質(zhì)因數(shù)分解。輸入格式輸入兩個(gè)整數(shù)a，b。輸出格式每行輸出一個(gè)數(shù)的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是從小到大的)(具體可看樣例)樣例輸入310樣例輸出3=34=2*25=56=2*37=78=2*2*29=3*310=2*5提示先篩出所有素?cái)?shù)，然后再分解。數(shù)據(jù)規(guī)模和約定2<=a<=b<=10000#include<iostream>#include<cmath>usingnamespacestd;intzs[10001];intk;//遞歸求因數(shù)stringpri(intm){ inti;if(m==1)return"";for(inti=0;i<k;i++){if(m%zs[i]==0){cout<<zs[i];if(m/zs[i]!=1)cout<<"*";returnpri(m/zs[i]);}}}//篩選出質(zhì)數(shù)voidzhishu(inta,intb){inti,j;k=0;for(i=2;i<=b;i++){ints=sqrt(i);for(j=2;j<=s;j++)if(i%j==0)break;if(j>s){zs[k]=i;k++;}}}intmain() {inta,b,i;cin>>a>>b;zhishu(a,b);for(i=a;i<=b;i++){cout<<i<<"=";pri(i);cout<<endl;}return0;}FJ的字符串（遞歸）問(wèn)題描述FJ在沙盤(pán)上寫(xiě)了這樣一些字符串：A1=“A”A2=“ABA”A3=“ABACABA”A4=“ABACABADABACABA”……你能找出其中的規(guī)律并寫(xiě)所有的數(shù)列AN嗎？輸入格式僅有一個(gè)數(shù)：N≤26。輸出格式請(qǐng)輸出相應(yīng)的字符串AN，以一個(gè)換行符結(jié)束。輸出中不得含有多余的空格或換行、回車(chē)符。樣例輸入3樣例輸出ABACABA#include<iostream>#include<cstdio>usingnamespacestd;voidprint(intn){if(n==1){printf("A");return;}else{print(n-1);//遞歸printf("%c",'A'+n-1);print(n-1);}}intmain() {intn; scanf("%d",&n);print(n);}完美的代價(jià)（貪心思想）問(wèn)題描述回文串，是一種特殊的字符串，它從左往右讀和從右往左讀是一樣的。小龍龍認(rèn)為回文串才是完美的。現(xiàn)在給你一個(gè)串，它不一定是回文的，請(qǐng)你計(jì)算最少的交換次數(shù)使得該串變成一個(gè)完美的回文串。交換的定義是：交換兩個(gè)相鄰的字符例如mamad第一次交換ad:mamda第二次交換md:madma第三次交換ma:madam(回文！完美！)輸入格式第一行是一個(gè)整數(shù)N，表示接下來(lái)的字符串的長(zhǎng)度(N<=8000)第二行是一個(gè)字符串，長(zhǎng)度為N，且只包含小寫(xiě)字母輸出格式如果可能，輸出最少的交換次數(shù)。否則輸出Impossible樣例輸入5mamad樣例輸出3#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;//貪心思想，從左向右遍歷，對(duì)于當(dāng)前字符，從最右邊向左遍歷，找到與當(dāng)前字符相同的，把它移動(dòng)到正確位置，累加步數(shù)。 //如果字符串長(zhǎng)度為偶數(shù)，只要有一個(gè)無(wú)法配對(duì)的字符，就不能變成回文串，若為奇數(shù)，只要出現(xiàn)兩個(gè)無(wú)法配對(duì)的字符，也不能。intmain(){charch[8010];intn,sum=0,ok=1,c=-1;scanf("%d%s",&n,ch);inti,j=n–1,k; //mamad for(i=0;i<=j-1;i++){ //從左向右依次判斷 for(k=j;k>=i;k--){//從最右邊查找，看有無(wú)與當(dāng)前字符相同的if(k==i){//沒(méi)有找到與ch[i]相同的字符if(n%2==0||c!=-1){//若n為偶數(shù)或ch[i]不是唯一無(wú)法匹配的字符ok=0;break;}c=1; //n為奇數(shù)，ch[i]為第一個(gè)無(wú)法匹配的字符sum+=n/2-i;//將它移到中間所需步數(shù)break;}if(ch[k]==ch[i]){ //找到相同的 for(intt=k;t<=j-1;t++) ch[t]=ch[t+1];//貪心思想，往后移到對(duì)稱(chēng)位置sum+=j-k;j--;break;}}if(!ok)break;}if(!ok)printf("Impossible\n");elseprintf("%d\n",sum);return0;}Sine之舞（技巧）問(wèn)題描述最近FJ為他的奶牛們開(kāi)設(shè)了數(shù)學(xué)分析課，F(xiàn)J知道若要學(xué)好這門(mén)課，必須有一個(gè)好的三角函數(shù)基本功。所以他準(zhǔn)備和奶牛們做一個(gè)“Sine之舞”的游戲，寓教于樂(lè)，提高奶牛們的計(jì)算能力。不妨設(shè)An=sin(1–sin(2+sin(3–sin(4+...sin(n))...)Sn=(...(A1+n)A2+n-1)A3+...+2)An+1FJ想讓奶牛們計(jì)算Sn的值，請(qǐng)你幫助FJ打印出Sn的完整表達(dá)式，以方便奶牛們做題。輸入格式僅有一個(gè)數(shù)：N<