- 論壇徽章:
- 0
|
本來是想寫個《C語言經(jīng)典題目系列》，本系列包括一些經(jīng)典算法題目，但由于時間問題，現(xiàn)在只是收集了不多題目且只做了一部分，就先發(fā)上來了。寫此目的幫助一些學c語言的人入門及運用一些算法，由于水平有限錯誤在所難免及本來這些題目不是很難高手就不用看了，其中錯誤歡迎大家指正。
1、
【問題描述】梯有N階，上樓可以一步上一階，也可以一步上二階。編寫一個程序，計算共有多少中不同的走法
【思路】看到此題目容易想到用遞歸的方法來做，因為遞歸是一種描述和解決結(jié)構(gòu)自相似問題的基本算法，而N階樓梯問題和N-1階、N-2階的結(jié)構(gòu)完全相同。
解決遞歸問題可以分為兩個部分，第一部分是一些特殊（基礎(chǔ)）情況，用直接法解，即始基；第二部分與原問題相似，可用類似的方法解決（即遞歸），但比原問題的規(guī)模要小。
定義int count(int n)函數(shù)求解N階樓梯的走法，基于上述思想，可知：
- N階樓梯問題的始基是N==1、N==2兩種情況；
- 上樓可以一步上一階，也可以一步上二階，當上一階時問題規(guī)模變?yōu)镹-1，當上二階時問題規(guī)模變?yōu)镹-2，所以總的情況為count(n-1)+count(n-2)。
【代碼】
cCODE:
| #include<stdio.h>
#include<stdlib.h>
int count(int n);
/*count how many ways to climb up N steps stairs.*/
int main (int argc, char *argv[])
{
int n,ct;
printf("please input n:\n");
scanf("%d",&n);
ct=count(n);
printf("there are %d ways to climb up N steps stairs!\n",ct);
system("PAUSE");
return 0;
}
int count(int n)
{
if(1==n)
return 1;
else if(2==n)
return 2;
else return count(n-1)+count(n-2);
} |
【程序輸入輸出】for example
please input n:
5
there are 8 ways to climb up N steps stairs!
2、
【問題描述】Armstrong數(shù)具有如下特征：一個n位數(shù)等于其個位數(shù)的n次方之和。如：
153＝13＋53＋33
1634＝14＋64+34+44
找出2、3、4、5位的所有Armstrong數(shù)。
【思路】看到此題我第一反應是用枚舉法，給定m(10<=m<=99999)，首先判斷m的位數(shù)n，然后判斷它是否等于各位數(shù)的n次方之和。- 定義函數(shù)int judgeDigit(int m)，用于判斷給定參數(shù)m的位數(shù)；
- 定義函數(shù)int judgeEqual(int m,int n)，其中m為給定的數(shù)，n為m的位數(shù)，用于判斷m是否等于各位數(shù)的n次方之和。
【代碼】
cCODE:
|
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int judgeDigit(int m);
/*This function return the digit of parameter m*/
void judgeEqual(int m,int n);
/*parameter m is a integer,parameter n is the digit of m,this function is used to judge m whether is a Armstrong integer and output it*/
int main (int argc, char **argv)
{
int i,len;
printf("All 2 digit to 5 digit Armstrong integers are following:\n");
for(i=10;i<=99999;i++)
{
len=judgeDigit(i);
judgeEqual(i,len);
}
printf("\n");
system("PAUSE");
return 0;
}
int judgeDigit(int m)
{/*This function return the digit of parameter m*/
int len=0;
do
{
++len;
m=m/10;
}while(m);
return len;
}
void judgeEqual(int m,int n)
{/*parameter m is a integer,parameter n is the digit of m,this function is used to judge m whether is a Armstrong integer and output it*/
int j,temp=m,sum=0;
for(j=1;j<=n;j++)
{
sum+=(int)(pow(temp%10,n));
temp=temp/10;
}
if(m==sum)/*if m is equal to sum,that is to say m is a Armstrong integer*/
printf("%d\t",m);
}
|
【程序輸入輸出】
no input；
output：
All 2 digit to 5 digit Armstrong integers are following:
153 370 371 407 1634 8208 9474 54748 92727 93084
注：用gcc調(diào)試就得不到153這個結(jié)果，但windows下用vc6.0就可以得到。不解中，這是編譯器問題還是程序問題？
3、
【問題描述】將1,2,3,4,5,6,7,8,9共9個數(shù)分成三組,組成3個三位數(shù),且使這3個三位數(shù)構(gòu)成1:2:3的比例,例如:3個三位數(shù)192,384,576滿足以上條件.192:384:576=1:2:3。試求出所有滿足條件的3個三位數(shù)。
【思路】1～9組成的最小三位數(shù)是123，最大的是987，由于要滿足1：2：3的關(guān)系，最小的那個數(shù)應該不到于987/3＝329。這樣的話第一個數(shù)的變化范圍是123～329，將這里面的數(shù)分別乘2、乘3，然后判斷這三個數(shù)是否符合要求，即這三個數(shù)是否由1～9組成，而且各個數(shù)字不能相同。
即對每個數(shù)n(123<=n<=329)用枚舉法。
- 定義函數(shù)int judge(int n)，用于判斷整數(shù)n的各位數(shù)字是否相同，如果有想同的就返回0；否則返回1；
- 對每個數(shù)n(123<=n<=329)，2*n，3*n調(diào)用judge()函數(shù)用于判斷這三個數(shù)是否由1~9組成且各個數(shù)字不相同；
- 判斷n，2*n，3*n這三個數(shù)中的各位數(shù)是否相同，所以對數(shù)n*1000*1000+2*n*1000+3*n調(diào)用judge()判斷。
所以(judge(n)==0||judge(2*n)==0||judge(3*n)==0||judge(n*1000+2*n*100+3*n)==0)為真的話，即其中給定的n不符合要求。其實只要(judge(n*1000+2*n*100+3*n)==0)這一個條件即可，因為它包含了前面兩種情況。
caution：其實要判斷這三個數(shù)是否由1~9組成且各個數(shù)組不相同，即這三個數(shù)的各位數(shù)是否覆蓋了1~9，只要判斷各位數(shù)字的積是否等于9！且各位數(shù)字的和是否等于45。
【代碼】
cCODE:
| #include<stdio.h>
#include<stdlib.h>
int judge(int n);
int main (int argc, char **argv)
{
int l,m,n,p,q;
for(l=123;l<=329;l++)
{
m=2*l,n=3*l;
p=l*1000+m,q=p*1000+n;
if(judge(q)==0)
//判斷l(xiāng)、m、n是否符合要求。如果不符合就跳出本次循環(huán)，進入下次循環(huán)
continue;
printf("%d,%d,%d\n",l,m,n);
}
system("PAUSE");
return 0;
}
int judge(int n)
{//用于判斷整數(shù)n的各位數(shù)字是否相同，如果有想同的就返回0；否則返回1
int num[10],i,j,len=0,temp=n;
do
{
++len;
temp=temp/10;
}while(temp);//求出n的位數(shù)
for(i=1;i<=len;i++)
{//將n的各位數(shù)字存入num［］，并判斷是否存在0及相同的數(shù)字，如果存在就返回0
if((num=n%10)==0)
return 0;
n=n/10;
for(j=1;j<i;j++)
if(num[j]==num)
return 0;
}
return 1;
} |
cCODE：來自一位網(wǎng)友youshuang，即用判斷各位數(shù)字的積是否等于9！且各位數(shù)字的和是否等于45。)
| #include <stdio.h>
bool judge( int a, int b, int c )
{
char tmp_buf[ 10 ];
sprintf( tmp_buf, "%d%d%d", a, b, c );
int nTimeResult = 1;
int nSumResult = 0;
for ( int i = 0; i < 9; i++ )
{
nTimeResult *= ( tmp_buf[ i ] - '0' );
nSumResult += ( tmp_buf[ i ] - '0' );
}
return ( ( nTimeResult == 362880 ) && ( nSumResult == 45 ) );
}
int main()
{
for ( int i = 123; i <= 329; i++ )
{
if ( judge( i, i * 2, i * 3 ) )
{
printf( "%d, %d, %d \n", i, i * 2, i * 3 );
}
}
return 0;
} |
【程序輸入輸出】
no input；
output：
192,384,576
219,438,657
273,546,819
327,654,981
4、
【問題描述】和尚挑水
某寺廟里7個和尚:輪流挑水，為了和其他任務不能沖突，各人將有空天數(shù)列出如下表：
和尚1: 星期二,四;
和尚2: 星期一,六;
和尚3: 星期三,日;
和尚4: 星期五;
和尚5: 星期一,四,六;
和尚6: 星期二,五;
和尚7: 星期三,六,日;
請將所有合理的挑水時間安排表
【思路】用回朔法求解（遞歸方式實現(xiàn)，當然也可以用迭代方式）。用結(jié)構(gòu)體存儲和尚的信息（空閑時間、是否已經(jīng)挑過水標記）回朔法即每進行一步，都試圖在當前部分解的基礎(chǔ)上擴大該部分解。擴大時，首先檢查擴大后是否違反了約束條件，若不違反，則擴大之，然后繼續(xù)在此基礎(chǔ)上按照類似的方法進行，直至成為完整解；若違反，則放棄該步以及它所能生成的部分解，然后按照類似的方法嘗試其他可能的擴大方式，直到嘗試了所有的擴大方式�！ �
【代碼】
cCODE:
| #include<stdio.h>
#include<stdlib.h>
void backtrack(int n);
/*函數(shù)功能：回朔求解第n天至第7天的解（即第n～7天分別安排和尚幾）*/
struct st
{
int spare[8];
/*存儲和尚的空閑時間，spare=0表示星期i沒有空閑，spare=1表示星期i空閑,其中spare[0]不用*/
int flag;
/*用于標記和尚周內(nèi)是否已經(jīng)工作過，flag＝0表示沒挑過水，flag＝1表示已經(jīng)挑過水*/
}monk[8];
int x[8],sum=0;/*sum用于統(tǒng)計共有多少種方案*/
int main (int argc, char **argv)
{
int i,j;
for(i=1;i<=7;i++)
{/*初始化和尚的空閑時間,初始化時和尚全部沒挑過水即flag都為0*/
printf("請輸入和尚%d的空閑時間：",i);
for(j=1;j<=7;j++)
{
scanf("%d",&monk.spare[j]);
}
monk.flag=0;
}
backtrack(1);
printf("共有%d種方案\n",sum);
}
void backtrack(int n)
{/*函數(shù)功能：回朔求解第n天至第7天的解（即第n～7天分別安排和尚幾）*/
int j;
if(n>7)
{
sum++;
printf("方案%d:\n",sum);
for(j=1;j<=7;j++)
{
printf("星期%d和尚%d挑水\n",j,x[j]);
}
printf("\n");
}
else
{
for(j=1;j<=7;j++)
{
x[n]=j;
if(monk[j].flag==0&&monk[j].spare[n]==1)
{//判斷和尚j是否已經(jīng)挑過水及和尚星期n是否有空
monk[j].flag=1;
backtrack(n+1);
monk[j].flag=0;
}
}
}
} |
【程序輸入輸出】
input:
請輸入和尚1的空閑時間：0 1 0 1 0 0 0
請輸入和尚2的空閑時間：1 0 0 0 0 1 0
請輸入和尚3的空閑時間：0 0 1 0 0 0 1
請輸入和尚4的空閑時間：0 0 0 0 1 0 0
請輸入和尚5的空閑時間：1 0 0 1 0 1 0
請輸入和尚6的空閑時間：0 1 0 0 1 0 0
請輸入和尚7的空閑時間：0 0 1 0 0 1 1
output:
方案1:
星期1和尚2挑水
星期2和尚6挑水
星期3和尚3挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚5挑水
星期7和尚7挑水
方案2:
星期1和尚2挑水
星期2和尚6挑水
星期3和尚7挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚5挑水
星期7和尚3挑水
方案3:
星期1和尚5挑水
星期2和尚6挑水
星期3和尚3挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚2挑水
星期7和尚7挑水
方案4:
星期1和尚5挑水
星期2和尚6挑水
星期3和尚7挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚2挑水
星期7和尚3挑水
共有4種方案
5、
【問題描述】編寫一個c程序，利用如下的格里高利公式求п的值，直到最后一項的值小于10-6為止。
【思路】由公式可以看出，![]() 每次n的值都會改變，這實際上就是迭代。
在程序設(shè)計中，迭代是經(jīng)常使用的一種算法。使用迭代算法時要注意三個問題：
- 迭代的初始值，如本題中sum的初始值為1，n的初始值為1
- 迭代公式，這是迭代的關(guān)鍵，如果有幾個迭代公式，要特別注意這些迭代的順序。如i+=1和sum+=n的次序不能交換。
- 迭代終止條件。一般用一個表達式或者計數(shù)器來判斷迭代式是否應該終止。
本題中迭代式中i+=1，i的初始值為1；![]() sum+=n or sum-=n這通過一個標志變量flag來控制，flag==1時sum+=n，flag==0時sum-=n，sum的初始值為1。終止條件為![]() 。
【代碼】
cCODE:
| #include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main (int argc, char **argv)
{
int flag=0,i=1;
double n=1,sum=1;
while(n>=pow(10,-6))
{
n=(double)1/(2*i+1);
i+=1;
if(1==flag)
{
sum+=n;
flag=0;
}
else
{
sum-=n;
flag=1;
}
}
sum*=4;
printf("%lf",sum);
system("PAUSE");
return 0;
}
|
【程序輸入輸出】
No input；
Output：
3.141595
6、
【問題描述】編寫一個c程序，把下列數(shù)組延長到第50項：
1，2，5，10，21，42，85，170，341，682
【思路】由給定的數(shù)組元素可以看出偶數(shù)項是前一項的2倍，奇數(shù)項是前一項的2倍加1。
即![]() ，這是一中遞推關(guān)系由前項推出后項，此題可以通過遞推關(guān)系求解。
遞推解題和迭代解題是很相似的，遞推是通過其他變量來演化，而迭代則是通過自身不斷演化。遞推法的運用也有三個關(guān)鍵：
- 尋找遞推關(guān)系。這是最重要的問題。遞推關(guān)系有解析和非解析兩種。解析遞推關(guān)系是指能用一般數(shù)學公式描述的關(guān)系，也稱遞推公式。例如，本題的遞推關(guān)系就是解析的。非解析遞推關(guān)系是指不能用一般的數(shù)學公式描述的關(guān)系，這類關(guān)系的描述，也許本身就是一個過程。這類問題一般比較復雜，要結(jié)合其他的策略如分治法來解決。
- 遞推關(guān)系必須有始基，即最小子解（針對初始規(guī)模的子解的值），沒有始基，遞推計算就不能開始。例如本題a1=1就是始基。
- 遞推計算。即根據(jù)遞推關(guān)系進行遞推計算。遞推計算可以由遞歸解析和非遞歸兩種，遞歸計算是采用遞歸法，其形式是自頂向下，而非遞歸則是自底向上。本題是非遞歸的。
解此題還須注意一點：數(shù)列的項必須定義為double型，因為延長到第50項如果定義為int or float型，數(shù)列的項會被截斷即超過int和float的表示范圍。
【代碼】
cCODE:
| #include<stdio.h>
#include<stdlib.h>
int main (int argc, char **argv)
{
double a1=1,a=0;
int i=1;
while(i<=50)
{
printf("%.0lf ",a1); //'.0’ is just for do not output the decimal place
i++;
if(i%2==1)
a=2*a1+1;
else
a=2*a1;
a1=a;
}
system("PAUSE");
return 0;
}
|
【程序輸入輸出】
No input；
Output：
1 2 5 10 21 42 85 .......（略）
7、
【問題描述】 用遞歸算法實現(xiàn)求一個數(shù)組中的最大元素。
【思路】解決遞歸問題可以分為兩個部分，第一部分是一些特殊（基礎(chǔ)）情況，用直接法解，即始基；第二部分與原問題相似，可用類似的方法解決（即遞歸），但比原問題的規(guī)模要小。
本題顯然始基是a[0],關(guān)鍵是要找出遞歸關(guān)系，定義一個函數(shù)int max(int a[],int n)，其中整型a[]是一個數(shù)組，n是數(shù)組長度減1，即數(shù)組最大有效元素的下標，因為c語言中數(shù)組元素下標是從0開始的。
- 如果0==n，則a[0]就是最大的元素
- 如果n>0，則先求出a[0]到a[n-1]的最大元素，然后與a[n]比較，較大者即為最大元素。其中a[0]到a[n-1]又可以用這種方式求，此時需要將a[0],a[1]...a[n-1]看成一個由n-1個元素構(gòu)成的一維數(shù)組。
【代碼】
cCODE:
| #include<stdio.h>
#include<stdlib.h>
int max(int a[],int n);
int main (int argc, char **argv)
{
int a[]={1,2,3,4,5,6,7,6};
printf("The max element is %d!\n",max(a,7));
/*caution:he length of a is 8,but the argument is 7*/
system("PAUSE");
return 0;
}
int max(int a[],int n)
{
if(0==n)
return a[n];
else
return (a[n]>max(a,n-1)?a[n]:max(a,n-1));
}
|
【程序輸入輸出】
no input;
output:
The max element is 7!
8、
【問題描述】自然數(shù)的拆分：任何一個大于1的自然數(shù)N，總可以拆分成若干個自然數(shù)之和，并且有多種拆分方法。例如自然數(shù)5，可以有如下一些拆分方法：
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+4
5=2+3
【思路】自然數(shù)的拆分可以用回溯法。
知識點：回溯法解題時，對任一解的生產(chǎn)，一般采用逐步擴大解的方式。每進行一步，都試圖在當前部分解的基礎(chǔ)上擴大該部分解。擴大時，首先檢查擴大后是否違反了約束條件，若不違反，則擴大之，然后繼續(xù)在此基礎(chǔ)上按照類似的方法進行，直至為完全解；若違反，則放棄該步以及它生成的部分解，然后按照類似的方法嘗試其他可能的擴大方式，直到已經(jīng)嘗試了所有的擴大方式。
回溯法解題通常包含以下三個步驟：
- 針對所給問題，定義問題的解空間；如本題對5的拆分來說，1<=拆分的數(shù)<=5。
- 確定易于搜索的解空間結(jié)構(gòu)；如本題對5的拆分來說，用x[]數(shù)組來存儲解，每個數(shù)組元素的取值范圍都是1<=拆分的數(shù)<=5，從1開始搜索直到5。
- 搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。如本題對5的拆分來說，為了避免重復，x>=x[j](i>j)，如x[]={2,3}滿足條件而x[]={3,2}就不滿足條件不是可行解即無效。
回溯法通常有兩種實現(xiàn)方式，一種是遞歸的方式，另一種是迭代的方式。在此就用遞歸方式，當然迭代的方式也可以。
【代碼】cCODE:
| #include<stdio.h>
#include<stdlib.h>
void splitN(int n,int m);//n是需要拆分的數(shù)，m是拆分的進度。
int x[1024]={0},total=0 ;//total用于計數(shù)拆分的方法數(shù)，x[]用于存儲解
int main()
{
int n ;
printf("please input the natural number n:");
scanf("%d",&n);
splitN(n,1);
printf("There are %d ways to split natural number %d.\n",total,n);
system("PAUSE");
return 0 ;
}
void splitN(int n,int m)
{//n是需要拆分的數(shù)，m是拆分的進度。
int rest,i,j;
for(i=1;i<=n;i++)
{//從1開始嘗試拆分。
if(i>=x[m-1])
{//拆分的數(shù)大于或等于前一個從而保證不重復
x[m]=i ;//將這個數(shù)計入結(jié)果中。
rest=n-i ;//剩下的數(shù)是n-i，如果已經(jīng)沒有剩下的了，并且進度(總的拆分個數(shù))大于1，說明已經(jīng)得到一個結(jié)果。
if(rest==0&&m>1)
{
total++;
printf("%d\t",total);
for(j=1;j<m;j++)
{
printf("%d+",x[j]);
}
printf("%d\n",x[m]);
}
else
{
splitN(rest,m+1);//否則將剩下的數(shù)進行進度為m+1拆分。
}
x[m]=0;//取消本次結(jié)果，進行下一次拆分。環(huán)境恢復，即回溯
}
}
} |
【程序輸入輸出】
input:
please input the natural number n:5
output:
1 1+1+1+1+1
2 1+1+1+2
3 1+1+3
4 1+2+2
5 1+4
6 2+3
There are 6 ways to split natural number 5.
[ 本帖最后由 吳秦 于 2009-7-1 17:44 編輯 ] |
|
免費注冊
發(fā)表于 2009-06-30 03:10
發(fā)表于 2009-06-30 13:17
