C程序設計例解

2019-11-17 05:20:09

字體：大中小

來源：轉載

供稿：網友

在程序設計過程中，類似于解決其它復雜的智力問題，我們使用推測、直覺、技巧、靈感和經驗在內的各種技巧和技術，最經常使用的工具是抽象技術。一般地，在開始階段，因還未了解問題的全部細節和求解的方法，主要問題集中于對問題的求解方案的全局作出決策，設計出大概的求解步聚，這是非常抽象的算法。其中有許多細節還不明確，只是用結構化的控制結構將若干抽象的計算步聚有機地聯系起來。在抽象的計算步聚中，只是確定了計算的目標，而所指的操作對象和數據結構通常還是未確定的。以計算目標為線索，對抽象計算步聚作進一步的深入考慮，可能會引入數據結構和操作對象，并給也更具體的計算過程的描述。其中也許依舊包含有某些抽象計算步聚，但與原來的計算步聚相比，在規模及難度上已有所降低。對新產生的抽象計算步聚作進一步的深入考慮和分解，如此循序漸近，計算步聚、操作對象和數據結構會越來越明確，抽象的東西會越來越少，直至有關細節都已確定后設計過程才算結束，隨后的工作是程序編碼。
由此看來，程序設計的開始階段最重要的就是確定算法和使用何種數據結構，只要這個過程完成得很好，隨后的程序代碼編寫工作也就會很輕松了。所以學習時要從例子中得到啟發，了解如何設計算法、設計數據結構、最終編出程序或函數的設計過程。

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

01. 試按以下給出的基數排序算法思想為整數鏈表編寫一個排序函數
解：
基數排序是按表元鍵值的各位值進行排序。
設有一個整數鏈表，其中表元的鍵值為不超過三位數的整數，不妨設鍵值形式ABC。其中A表示鍵值的百位數，B為十位數，C為個位數。首先按鍵值中的個位值C對鏈表作分拆和鏈接，先把鏈表分拆成多至10個隊列鏈表，然后以C的值從0至9的順序把分拆后的十個隊列鏈表重新收集成一個鏈表。接著依次對鍵值中的B和A進行同樣的分拆和鏈接操作，則最后收集起來的鏈表是按鍵值從小到大排序鏈接的。如有一個鏈表按它們的鍵值其表元的鏈接順序依次為：
153 678 56 288 457 653 721 876 433 254
按它們的鍵值的個位分拆，得到十個隊列鏈表，列出它們的鍵值順序有：
0：空鏈表
1： 721
2：空鏈表
3： 153 653 433
4： 254
5：空鏈表
6： 56 876
7： 457
8： 678 288
9：空鏈表
順序將它們收集一起后，鏈表的鍵值順序有：
721 153 653 433 254 56 876 457 678 288
再按它們鍵值的十位分拆，得到十個隊列鏈表，列出它們的鍵值順序有：
0：空鏈表
1：空鏈表
2： 721
3： 433
4：空鏈表
5： 153 653 254 56 457
6：空鏈表
7： 876 678
8： 288
9：空鏈表
順序將它們收集在一起后，鏈表的鍵值順序有：
721 433 153 653 254 56 457 876 678 288
再按它們鍵值的百位分拆，得到十個隊列鏈表，列出它們的鍵值順序有：
0： 56
1： 153
2： 254 288
3：空鏈表
4： 433 457
5：軍分區邊表
6： 653 678
7： 721
8： 876
9：空鏈表
順序將它們收集一起后，鏈表的鍵值順序有：
56 153 254 288 433 457 653 678 721 876
這是一個按鍵值從小到大鏈接的鏈表。
基數排序主要包含以下控制過程，主循環控制對鍵值順序從低位高位的重復操作，在主循環內包含兩個計算步聚：按鍵值的當前位置分拆鏈表為十個隊列鏈表，將對應0至9的十個隊列鏈表收集成一個鏈表。用算法形式描述其計算過程如下：
算法--基數排序
{
依次對鍵值的個位到高位逐位循環
{
按鍵值的當前位將鏈表分拆成十個隊列鏈表；
按對應0至9的順序將十個鏈表收集成一個鏈表；
}
}
由于分拆時，當前表元接在對應值的隊列鏈表的末尾，為了便于為每個隊列鏈表接入新表元，除每個隊列鏈表有首指針外，還應為每個隊列鏈表引入末表元指針。又為了能方便處理十個隊列，十個隊旬的頭和尾指針又分別構成兩個指針數組。按對應值0至9 的順序將十個鏈表收集成一個鏈表的工作只要將空鏈表除外，順序將這些鏈表的首尾鏈接即可。另外，編寫函數需要知道鏈表的首指針，但排序后鏈表中各表元的鏈接順序會改變，原來的首表元可能不再是首表元，即鏈表的首指針也會改變，所以函數的參數應為鏈表首指針的指針。
程序代碼如下：
#include<stdio.h>
#include<stdlib.h>
#define KEYN 3
strUCt ele{
int key;
struct ele *link;
};
void basesort(struct ele **h)
{
int i,j,factor;
struct ele *head[10],*tail[10],*p,*u;
/*依次對鍵值的個位到高位逐位循環*/
for(i=0,factor=1,p=*h;i<KEYN;factor*=10,i++)
{
/*按鍵值的當前值將鏈表分拆成十個隊列鏈表*/
for(j=0;j<10;j++) /*預置十個空鏈表*/
head[j]=NULL;
while(p)
{ /*將*p接到某隊列鏈表*/
u=p->link; /*保護下一個表元的指針*/
j=(p->key/factor)%10; /*求表元鍵值的當前位*/
if(head[j]==NULL) /*按當前位值將*p接在對應隊列的末尾*/
head[j]=p;
else
tail[j]->link=p;
tail[j]=p;
p->link=NULL;
p=u; /*預備訪問下一表元*/
}
/*將十個隊列鏈表鏈接成一個鏈表*/
p=NULL;
for(j=0;j<10;j++)
{
if(head[j]==NULL)continue; /*跳過空鏈表*/
if(p==NULL)p=head[j];
else u->link=head[j]; /*各鏈表首尾順序鏈接*/
u=tail[j];
}
}
*h=p;
}
int a[]={35,298,832,932,38,635,22,15,48};
#define N sizeof a/sizeof a[0]
void main()
{
struct ele *h,*u;
int i;
h=NULL; /*先形成一個空鏈表*/
for(i=0;i<N;i++)
{ /*任意形成一個鏈表*/
u=(struct ele *)malloc(sizeof(struct ele));
u->key=a[i];
u->link=h;
h=u;
}
basesort(&h); /*排序*/
for(u=h;u;u=u->link) /*順序輸出鏈表各表元的鏈值*/
printf("/n");
}

程序運行結果為：
15 22 35 38 48 298 635 832 932

02.找一個最小的自然數x，使它等于不同的兩對自然數的三次冪之和，即使得：
x=a*a*a+b*b*b=c*c*c+d*d*d
其中a,b,c,d都是自然數，且有a!=c和a!=d
解：
問題要找的解是兩個自然數對，以自然數對為解的候選者，如程序能這樣枚舉解的候選者，使枚舉出來的自然數對的三次冪之和構成一個不減的序列，則當發現兩個自然數對的三次冪之和相等時，這兩對自然數就是問題的解。將這種思想寫成抽象算法描述如下：
{
i1=1;j1=1;x=i1*i1*i1+j1*j1*j1;
do
{
i0=i1;j0=j1;min=x; /*保存上一個解的候選者*/
確定下一對自然數i1,j1;
x=i1*i1*i1+j1*j1*j1;
}while(x!=min);
printf("%d=%d^3+%d^3=%d^3+%d^3/n",x,i0,j0,i1,j1);
}
問題已轉化成如何按上述要求逐一自然數對。
為了尋找產生候選者規則的線索，將問題簡化為找一個最小的自然數x，使它等于不同的兩對自然數的平方之和。下面列出部分兩個自然數的平方之和的數表s[]，其中：
s[i][j]=i*i+j*j
C程序設計例解（圖一）

06.設有大小不等的X，Y，Z三個無刻度的油桶，分別能夠盛滿油X，Y，Z(例如，X=80，Y=50，Z=30)，并約定X>Y>Z。初始時，僅X油桶盛滿油，Y和Z油桶為空。要求程序尋找一種最少的分油步聚，在某個油桶中分出T升油(例如T=40)。
解：
令三個油桶的盛油情況為倒油過程的狀態，則倒油過程就是狀態變化的過程。為了記錄倒油過程，程序引入倒油狀態隊列，將倒油過程中產生的狀態存儲在隊列中。隊列的每個元素記錄每次分油后各個油桶的分油后各個油桶的盛油量和倒油軌跡等有關信息。程序反復從隊列中取出第一個還未檢查過的狀態，對該狀態下的每個油桶判定其是否可以倒出油，及是否可以倒進油。由于油桶沒有刻度，分油時只能將某個油桶倒滿或倒空。程序分別按倒空或倒滿兩種可能的倒油動作執行不同的處理，產生新的倒油狀態，為避免某個倒油狀態在隊列中重復出現，程序只將未曾出現過的新狀態及其倒油軌跡信息存入隊列中，假定程序檢查了相當多的狀態后，或能找到解，或能確定問題無解。

倒油程序算法如下：
算法---無刻度油桶分油
{
輸入各桶容量和目標容量；
將初始狀態存入倒油狀態隊列；
設置其它初始值；
do
{
對狀態隊列中第一個還未檢查的元素
在還未檢查完每個倒出的桶且還未找到解且還未確定無解情況下循環
if(倒出桶有油)
在還未檢查完每個桶且還未找到解且還未確定無解情況下循環
if(當前桶不是倒出桶且桶還有空)
{
確定本次倒油量；
在隊列中檢查倒油后的結果狀態是否在隊列中出現；
if(結果狀態不在隊列中出現)
{
將結果狀態和軌跡信息存入隊列；
if(有桶中的油達到目標容量)
設置找到解標志；
}
}
if(還未找到解)
{
修正隊列第一個還未檢查過的元素指針；
if(隊列中的元素都已檢查過)
設置無解標志；
}
}while(還未找到解且還未確定無解)；
if(找到解)
{
根據倒油步聚的軌跡信息，形成倒油步聚序列；
輸出倒油步聚序列；
}
}
倒油隊列中的元素應包含下列信息：各桶的盛油量，該狀態是從哪一個桶(源桶)倒向哪一個桶(目標桶)而形成的，形成該狀態的元素在隊列中的位置。根據以上算法編寫如下程序。

程序代碼如下：
#include<stdio.h>
#define N 100
#define BUCKETS 3
struct ele{
int state[BUCKETS]; /*各桶盛油量*/
int sbucket; /*源桶*/
int obucket; /*目標桶*/
int last; /*軌跡元素在隊列中的下標*/
}q[N]; /*隊列*/
int full[BUCKETS];
int i,j,k,found,unable,wi,wj,v,targ;
int head,tail;
void main()
{
/*輸入各桶容量和目標容量*/
printf("Enter volume of buckets./n");
for(i=0;i<BUCKETS;i++)
scanf("%d",&full[i]);
/*如要檢查full[0]>full[1]>full[2],相應代碼在此*/
printf("Enter volume of targ./n");
scanf("%d",&targ); /*檢查targ<=full[0]的代碼在此*/
/*設置將初始狀態存入倒油狀態隊列等初值*/
q[0].state[0]=full[0];
for(i=1;i<BUCKETS;i++)
q[0].state[i]=0;
q[0].sbucket=0;
q[0].obucket=0;
q[0].last=0;
found=unable=0;
head=tail=0;
do
{
/*對狀態隊列中第一個還未檢查過的元素在還未檢查完每個倒出的桶
且還未找到解且還未確定無解情況下循環*/
for(i=0;i<BUCKETS&&!found&&!unable;i++)
if(q[head].state[i]>0) /*倒出桶有油*/
/*在還未檢查完每個油桶且還未找到解且還未確定無解情況下循環*/
for(j=0;j<BUCKETS&&!found&&!unable;j++)
if(j!=i&&q[head].state[j]<full[j])
{ /*當前桶不是倒出桶且桶還有空*/
/*確定本次倒油量*/
if(q[head].state[i]>full[j]-q[head].state[j])
v=full[j]-q[head].state[j];
else v=q[head].state[i];
wi=q[head].state[i]-v;
wj=q[head].state[j]+v;
/*在隊列中檢查倒油后的結果狀態是否在隊列中出現*/
for(k=0;k<=tail;k++)
if(q[k].state[i]==wi&&q[k].state[j]==wj) break;
if(k>tail) /*結果狀態不在隊列中出現*/
{
/*將結果狀態和軌跡信息存入隊列*/
tail++;
q[tail].state[i]=wi;
q[tail].state[j]=wj;
q[tail].state[3-i-j]=q[head].state[3-i-j];
q[tail].sbucket=i+1;
q[tail].obucket=j+1;
q[tail].last=head;
/*如有桶達到目標盛油量，則設置找到解標志*/
if(wi==targwj==targ)found=1;
}
}
if(!found) /*還未找到解*/
{
head++; /*修正隊列第一個還未檢查過元素指針*/
if(head>tail) /*隊列中的元素都已檢查過*/
unable=1; /*設置無解標志*/
}
}while(!found&&!unable); /*還未找到解且還未確定無解*/
if(found) /*找到解*/
{
/*根據倒油步聚的軌跡信息，形成倒油步聚序列*/
i=tail;
j=-1;
do /*原倒油步聚逆向鏈接，現改為正向鏈接*/
{
k=q[i].last;
q[i].last=j;
j=i;
i=k;
}while(j);
/*輸出倒油步聚序列*/
for(k=q[k].last;k>=0;k=q[k].last)
{
printf("%5d to %2d:",q[k].sbucket,q[k].obucket);
for(i=0;i<BUCKETS;i++)
printf("%4d",q[k].state[i]);
printf("/n");
}
}
else printf("Unable!/n");
}
程序運行結果如下：
C程序設計例解（圖三）

QQ病毒騰訊QQ空間代碼專題 PPT教程專題 ADSL應用面面俱到 fireworks教程專題計算機和網絡技術基礎知識校園網專題網吧技術專題

07. 有2*n個盒子排成一行，其中有兩個相鄰的空盒，有n-1個盒子有符號'A'，有n-1個盒子有符號'B'。例如，n=5，并有初始配置如下：
A B B A . . A B A B
試編制程序，將輸入的盒子排列狀態按以下交換規則將全部‘A'放到全部‘B'的左邊，不管相鄰兩空盒的位置。交換規則是任意兩個非空相鄰盒子的內容可移入兩個空盒中，但移動時不得變更兩符號的前后次序。編寫程序輸入初始配置后，找出達到目標要求的最少交換次數的方案。
解：
從一種盒子排列出發，將其中兩個非空相鄰盒子中的內容移入空盒的每一種移動，會使盒子產生新的排列狀態，采用試探法窮舉所有可能的移動找問題的解。首先將盒子初始排列存入移動步聚表，然后是試探和回溯循環。循環工作內容有：檢查當前排列，若當前排列是要求的最終狀態，則將達到該狀態的移動步聚保存，并回溯去找更少移動步數的解。在試探超過限定的深度或當前狀態的所有可能移動都已試探窮盡情況下回溯；否則對當前狀態取其當前移動方法產生新的后繼狀態存入移動步聚表，并繼續向前試探。為能從某種排列出發，通過移動產生更接近目標要求的排列，對移動方法的選取作如下規定：
。擦過無意義的往返移動；
。不把兩個相鄰的同為符號‘A'的盒子向后移；
。不把兩個相鄰的同為符號‘B'的盒子向前移；
。不把兩個盒子移入到這樣的位置，移入后其首尾沒有一個與相鄰的盒子相同。
試探回溯找解算法如下：
算法---試探回溯找解
{
輸入初始排列；
初始狀態存入移動步聚表；
設置其它初值；
d=0; /*當前試探深，或當前狀態位置*/
do
{
if(當前狀態為盒子排列的終態)
{
保存解；
記錄當前解的試探深度；
回溯；
if(取盡所有可能的解)break;
}
if(試探深度超過設定值，或取盡當前狀態的所有選擇)
{
回溯；
if(取盡所有可能的選擇)break;
}
else
{
求新狀態的空盒位置；
取當前狀態的移動方法和當前狀態；
設定當前狀態的下一個移動方法；
擦過各種不希望的方法；
生成新狀態；
試探深度增1；
}
}while(1);
if(找到解)
輸出解；
}

程序代碼如下：
#include<stdio.h>
#include<string.h>
#define N 30
#define DEPTH 15
char b[2*N+1];
struct node
{
int empty; /*兩空盒的開始位置*/
char s[2*N+1]; /*盒子排列*/
int no; /*下一個移動開始的位，或稱移動方法*/
}q[DEPTH]; /*移動步聚表*/
char result[DEPTH][2*N+1]; /*存放解*/
char *s;
int best,empty,i,j,n,an,bn,sn,c,d;
void main()
{
printf("/nEnter N: ");
scanf("%d",&n);
printf("Enter initial state./n"); /*輸入初始狀態*/
for(an=bn=sn=i=0;i<2*n;)
{
c=getchar();
if(c==' ')
{
if(sn)continue; /*強制兩空白符連續出現*/
sn=1;
empty=i;
b[i++]='_';
b[i++]='_';
}
if(c=='A'c=='a')
{
if(an==n-1)continue; /*限制A的個數*/
an++;b[i++]='A';
}
if(c=='B'c=='b')
{
if(bn==n-1)continue; /*限制B的個數*/
bn++;b[i++]='B';
}
}
b[2*n]='/0';
strcpy(q[0].s,b); /*初始狀態存入移動步聚表*/
q[0].empty=empty;
q[0].no=0;
best=DEPTH-1; /*設定試探深度*/
d=0;
do
{
for(s=q[d].s; *s!='B';s++);
for(;*s&&*s!='A';s++);
if(*s=='/0') /*當前狀態為盒子排列的終態*/
{
for(j=0;j<=d;j++) /*保存解*/
strcpy(result[j],q[j].s);
best=d; /*記錄當前解的試探深度*/
d--; /*回溯*/
while(d>=0&&q[d].no==2*n-1)d--;
if(d<0)break; /*取盡所有可能的選擇*/
}
if(d>=bestq[d].no==2*n-1)
{
d--; /*回溯*/
while(d>=0&&q[d].no==2*n-1)d--;
if(d<0)break; /*取盡所有可能的選擇*/
}
else
{
empty=q[d].empty; /*新狀態的空盒位置*/
j=q[d].no++; /*取當前狀態的移動方法和設定新移動方法*/
if(d>=1&&q[d-1].empty==j)continue; /*擦過往返移動*/
s=q[d].s; /*取當前狀態*/
/*擦過各種不希望的移動*/
if(s[j]=='_'s[j+1]=='_')continue;
if(j<empty&&s[j]=='A'&&s[j+1]=='A')continue;
if(j>empty&&s[j]=='B'&&s[j+1]=='B')continue;
if(empty!=0&&s[empty-1]!=s[j]&&
(empty!=2*n-2&&s[empty+2]!=s[j+1]))continue;
if(empty==0&&s[j]=='B')continue;
if(empty==2*n-2&&s[j+1]=='A')continue;
/*生成新狀態*/
strcpy(q[d+1].s,q[d].s); /*形成移動后的狀態*/
q[d+1].s[empty]=q[d+1].s[j];
q[d+1].s[empty+1]=q[d+1].s[j+1];
q[d+1].s[j]=q[d+1].s[j+1]='_';
q[d+1].empty=j;
for(j=0;strcmp(q[j].s,q[d+1].s);j++);
if(j<=d)continue;
q[d+1].no=0;
d++; /*試探深度增1*/
}
}while(1);
if(best!=DEPTH-1)
{
printf("/n/n");
for(j=0;j<=best;j++)
printf("%s/n",result[j]);
}
}
程序運行結果如下：
C程序設計例解（圖四）