例65 方格填數
問題描述
給一個n*n的方格矩陣，還有n*n個整數，讓你將這些整數填入矩陣，使得每行每列每個對角線上整數的和都相等，下面給出幾個例子：
輸入
第一行一個整數n.（1<=n<=4)
第二行n*n個整數 ai (-10^8<=ai<=10^8)
輸出
第一行一個整數s 代表每行每列每個對角線的和值
接下來輸出一個n*n的矩陣，表示填數方案，
資料保證有解，可能存在多種方案，輸出字典序最小的（將每行順次相連之后，字典序最小）
輸入樣例
3
1 2 3 4 5 6 7 8 9
輸出樣例
15
2 7 6
9 5 1
4 3 8
（1）編程思路，
將輸入的n*n個整數保存到陣列a中，這n*n個整數的總和除以n的值保存到變數sum中，為了輸出時輸出字典序最小的，先將陣列a中的n*n個數按從小到大順序排列，這樣可以保證最先得到的可行解是字典序最小的，
之后按照從左到右從上到下的順序將n*n個數填寫到n*n個方格中，
撰寫遞回函式int dfs(int x, int y)，其功能是對方格（x,y）填寫數，每個格子可以在a[0]~a[n*n-1]中選取一個沒有填過的數a[i]（vis[i]=0時表示a[i]可以填寫）進行填寫，填寫后，遞回呼叫dfs(x,y+1)填寫下一個格子（若y=n，則遞回呼叫的下一個格子為dfs(x+1,1)），
在遞回呼叫程序中可以進行剪枝：在每一行或每一列填寫結束時，可以呼叫相應函式int chkRow(int row)或int chkCol(int col)判斷這一行或這一列之和是否等于 sum，若不等于，則直接回傳0，無需繼續搜索，
所有方格填寫結束后，判斷最后一行、最后一列和兩條對角線的和值是否都等于sum，若都等于，則找到一個可行解，回傳1，
（2）源程式，
#include <stdio.h>
#include <string.h>
int n, a[25], ans[5][5], sum;
int vis[25]={0};
int chkRow(int row)
{
int i,tmp = 0;
for (i=1; i<=n; i++)
tmp+= ans[row][i];
return tmp == sum;
}
int chkCol(int col)
{
int i,tmp = 0;
for (i=1; i<=n; i++)
tmp += ans[i][col];
return tmp == sum;
}
int chkX()
{
int i,tmp1 = 0, tmp2 = 0;
for (i=1; i<=n; i++) {
tmp1 += ans[i][i];
tmp2 += ans[i][n+1-i];
}
return tmp1 == sum && tmp2 == sum;
}
int dfs(int x, int y)
{
if (x==n+1 && y==1)
{
return chkRow(n) && chkCol(n) && chkX();
}
if (x > 1 && y == 1 && !chkRow(x-1)) return 0;
if (x == n && y > 1 && !chkCol(y-1)) return 0;
int xx = x, yy = y+1;
if (y==n) { xx=x+1; yy = 1; }
int i;
for (i=0; i<n*n; i++) {
if (!vis[i]) {
vis[i] = 1;
ans[x][y] = a[i];
if (dfs(xx, yy)) return 1;
vis[i] = 0;
}
}
return 0;
}
int main()
{
scanf("%d",&n);
int i,j,t;
for (i=0; i<n*n; i++) {
scanf("%d",&a[i]);
sum += a[i];
}
sum/= n;
for (i=0;i<n*n-1;i++)
for (j=0;j<n*n-1-i;j++)
if (a[j]>a[j+1]){
t=a[j]; a[j]=a[j+1]; a[j+1]=t;
}
dfs(1,1);
printf("%d\n",sum);
for (i=1; i<=n; i++) {
printf("%d",ans[i][1]);
for (j=2; j<=n; j++) {
printf(" %d",ans[i][j]);
}
printf("\n");
}
return 0;
}
習題65
65-1 數獨
問題描述
數獨是根據9×9 盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮內的數字均含1 - 9，不重復，每一道合格的數獨謎題都有且僅有唯一答案，推理方法也以此為基礎，任何無解或多解的題目都是不合格的，
芬蘭一位數學家號稱設計出全球最難的“數獨游戲”，并刊登在報紙上，讓大家去挑戰，
這位數學家說，他相信只有“智慧最頂尖”的人才有可能破解這個“數獨之謎”，
據介紹，目前數獨游戲的難度的等級有一到五級，一是入門等級，五則比較難，不過這位數學家說，他所設計的數獨游戲難度等級是十一，可以說是所以數獨游戲中，難度最高的等級，他還表示，他目前還沒遇到解不出來的數獨游戲，因此他認為“最具挑戰性”的數獨游戲并沒有出現，
輸入
一個未填的數獨，
輸出格式
填好的數獨，
輸入樣例
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0
輸出樣例
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
（1）編程思路，
定義二維陣列int map[10][10];來保存所填寫的數獨，輸入資料后，map[i][j]!=0表示格子（i,j）（0<=i<=8，0<=j<=8）已事先填寫了資料，map[i][j]==0表示格子（i,j）尚沒有填寫資料，需要在1~9中選擇一個數進行填寫，
撰寫遞回函式void dfs(int pos)對第pos個格子進行填寫，顯然，0<=pos<=80，當pos=81時，所有格子填寫完畢，輸出找到的解，同時置標志flag=1，這樣可以結束后續的搜索，不再找其他的可行解，
第pos個格子對應的坐標位置為（x=pos/9，y=pos%9），若map[x][y]!=0，則第pos個格子已預先填寫了資料，遞回呼叫dfs(pos+1)直接填寫下一個格子；若map[x][y]==0，則需要對第pos個格子填寫一個資料，此時將陣列vis[10]的元素先全部初始化為0，vis[i]=0表示數字i可以填寫，vis[i]=1表示數字i不能填寫在第pos個格子中，然后將第pos個格子所在行填寫過的數字map[x][k]對應的vis[map[x][k]]置為1，第pos個格子所在列填寫過的數字map[k][y]對應的vis[map[k][y]]置為1，還將第pos個格子所在的小3*3格子中填寫過的數字對應的vis元素也置為1，這樣可以選取1~9中某個vis[i]=0的數字i填寫到第pos個格子中，填寫后遞回呼叫dfs(pos+1)繼續填寫下一個格子，直到pos=81，所有格子填寫完畢，
（2）源程式，
#include <stdio.h>
#include <string.h>
int map[10][10];
int flag;
void dfs(int pos)
{
int i,j;
if (pos == 81){
for (i=0; i<9; i++){
for (j=0; j<9; j++){
printf("%d ",map[i][j]);
}
printf("\n");
}
flag = 1;
return ;
}
if (flag)
return ;
if (map[pos/9][pos%9]){
dfs(pos+1);
}
else{
int x=pos/9,y=pos%9;
int vis[10];
memset(vis,0,sizeof(vis));
for (i=0; i<9; i++){
if (x != i)
vis[map[i][y]] = 1;
if (y != i)
vis[map[x][i]] = 1;
}
int tx = x/3*3;
int ty = y/3*3;
for (i=0; i<3; i++){
for (j=0; j<3; j++){
if (tx+i==x && ty+j==y)
continue;
vis[map[tx+i][ty+j]] = 1;
}
}
for (i=1; i<=9; i++){
if (!vis[i]){
map[x][y] = i;
dfs(pos+1);
if (flag)
return ;
map[x][y] = 0;
}
}
}
}
int main()
{
int i,j;
for (i=0; i<9; i++){
for (j=0; j<9; j++)
scanf("%d",&map[i][j]);
}
flag =0;
dfs(0);
return 0;
}
65-2 地毯填補問題
問題描述
相傳在一個古老的阿拉伯國家里，有一座宮殿，宮殿里有個四四方方的格子迷宮，國王選擇駙馬的方法非常特殊，也非常簡單：公主就站在其中一個方格子上，只要誰能用地毯將除公主站立的地方外的所有地方蓋上，美麗漂亮聰慧的公主就是他的人了，公主這一個方格不能用地毯蓋住，毯子的形狀有所規定，只能有四種選擇（如圖）：
并且每一方格只能用一層地毯，迷宮的大小為2k ×2k的方形，當然，也不能讓公主無限制的在那兒等，對吧？由于你使用的是計算機，所以實作時間為1s，
輸入
輸入檔案共2 行，
第一行：k，即給定被填補迷宮的大小為2k ×2k （0<k≤10）；
第二行：x,y，即給出公主所在方格的坐標（x為行坐標，y為列坐標），x和 y之間有一個空格隔開，
輸出
將迷宮填補完整的方案：每一行為x y c（x,y為毯子拐角的行坐標和列坐標， c為使用毯子的形狀，具體見上面的圖1，毯子形狀分別用 1,2,3,4表示，x,y,c之間用一個空格隔開），
輸入樣例
3
3 3
輸出樣例
5 5 1
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
6 6 1
5 8 3
8 5 2
8 8 1
（1）編程思路，
大小為2k ×2k的迷宮可以分割成為4個2(k-1)*2(k-1)的小迷宮，分別標記為左上角迷宮，右上角迷宮、左下角迷宮和右下角迷宮，如圖1所示，
圖1 4個小迷宮
公主的位置必然在這四個小迷宮的某個迷宮內，其余三個小迷宮中沒有被公主占用，可以使用一個“L”型毯子覆寫在這三個小迷宮的匯合之處，這個“L”型毯子的3個小塊一定在每個小迷宮中放置1個，這樣可以將這三個小塊各看成一個“假公主”，這樣4個小迷宮中每個迷宮中均有1個位置被公主占用，由此可以將2k ×2k的迷宮地毯填補問題分割成為4個較小規模的2(k-1)*2(k-1)的小迷宮地毯填補問題，遞回這種分割，直至小迷宮轉化為1*1的1個格子，
例如，設公主在左上角的小迷宮中，這樣可以在其余3個小迷宮交匯處放置1個“1”行地毯，這樣每個小迷宮中均有1個格子放置了公主，如圖2所示，
圖2 公主在左上角迷宮中
進一步以樣例為例進行描述，樣例中公主的坐標為（3，3），位于左上角小迷宮中，左上角的4x4小迷宮中公主占了1格，就還剩15個方格，這樣15/3=5余0，則可以把地毯鋪完，按圖2思想，在剩下3個4x4的小迷宮的交匯處鋪上一個地毯（即(5,5,1)），使其各占1格，從16變為15格，這樣也可保證地毯可以正好鋪滿，然后對每個小迷宮各自進一步遞回，如圖3所示，
圖3 樣例的遞回示例
撰寫遞回函式void laying(int a,int b,int x,int y,int len)來鋪設地毯，其中引數a,b代表當前小迷宮的左上角頂點，x,y代表公主位置，len表示迷宮大小為len*len，
若x<=a+len/2-1 && y<=b+len/2-1，則公主在左上角小迷宮中，此時在其余3個小迷宮的交匯處鋪設一個“1”型地毯，用陳述句printf("%d %d 1\n",a+len/2,b+len/2);輸出即可，這樣原來大小為len*len的迷宮可以分割為4個(len/2)*(len/2)的小迷宮，因此遞回呼叫如下：
laying(a,b,x,y,len/2);
laying(a,b+len/2,a+len/2-1,b+len/2,len/2);
laying(a+len/2,b,a+len/2,b+len/2-1,len/2);
laying(a+len/2,b+len/2,a+len/2,b+len/2,len/2);
同理可以處理公主在右上角、左下角和右下角的情形，
需要注意的是按樣例的輸出，遞回的順序應該是左上角，右上角，左下角，右下角，
（2）源程式，
#include <stdio.h>
void laying(int a,int b,int x,int y,int len)
// a,b代表當前棋盤的左上角頂點，x,y代表公主位置
{
if (len==1) return ;
len=len/2;
if (x<=a+len-1 && y<=b+len-1) // 公主在左上角棋盤
{
printf("%d %d 1\n",a+len,b+len);
laying(a,b,x,y,len);
laying(a,b+len,a+len-1,b+len,len);
laying(a+len,b,a+len,b+len-1,len);
laying(a+len,b+len,a+len,b+len,len);
}
else if (x<=a+len-1 && y>b+len-1) // 公主在右上角棋盤
{
printf("%d %d 2\n",a+len,b+len-1);
laying(a,b,a+len-1,b+len-1,len);
laying(a,b+len,x,y,len);
laying(a+len,b,a+len,b+len-1,len);
laying(a+len,b+len,a+len,b+len,len);
}
else if (x>a+len-1 && y<=b+len-1) //公主在左下角棋盤
{
printf("%d %d 3\n",a+len-1,b+len);
laying(a,b,a+len-1,b+len-1,len);
laying(a,b+len,a+len-1,b+len,len);
laying(a+len,b,x,y,len);
laying(a+len,b+len,a+len,b+len,len);
}
else // 公主在右下角棋盤
{
printf("%d %d 4\n",a+len-1,b+len-1);
laying(a,b,a+len-1,b+len-1,len);
laying(a,b+len,a+len-1,b+len,len);
laying(a+len,b,a+len,b+len-1,len);
laying(a+len,b+len,x,y,len);
}
}
int main()
{
int m;
int k,x,y;
scanf("%d %d %d",&k,&x,&y);
m=1<<k;
laying(1,1,x,y,m);
return 0;
}
65-3 康托集
問題描述
康托集是由喬治·康托發現的，它是一種更簡單的分形，這是一個無限程序的結果，因此對于這個程式，列印整個集合的近似值就足夠了，以下步驟描述了輸出給定整數n所對應近似康托集的一種方法：
1）以長度為n3的一串破折號構成的虛線開始
2）將虛線的中間三分之一替換為空格，在原始字串的每一端留下一根由連續的破折號構成的虛線，
3）將每組虛線的中間三分之一再替換為空格，重復此操作，直到每組虛線由一個破折號組成，
例如，如果近似順序為3，則從包含27個破折號的字串開始：
---------------------------
將虛線中間三分之一變成空格 ：
--------- ---------
然后再將每組虛線中間三分之一變成空格：
--- --- --- ---
再來一遍：
- - - - - - - -
當破折號組的長度均為1時，此程序停止，輸出時不應該列印程式中的中間步驟，只應顯示上面最后一行給出的最終結果，
輸入
輸入包括多組測驗用例，每個測驗用例占一行，為一個介于0和12之間（包括0和12）的數字，
輸出
必須輸出康托集的近似值，后跟換行符，在康托集近似前后沒有空格，行中應該出現的唯一字符是“-”和“ ”，
輸入樣例
0
1
3
輸出樣例
-
- -
- - - - - - - -
（1）編程思路，
設S(n)表示長度為n3的近似康托集，顯然可以發現S(n)=S(n-1)+n*n*n/3個空格+S(n-1)，
撰寫遞回函式void cantor(int s,int e)，引數s和e分別表示描述近似康托集字串的開始位置和結束位置，顯然若e-s==1，字串中1個字符，直接賦值為“-”，遞回呼叫結束；否則，分別對前三分之一進行遞回呼叫cantor(s,s+(e-s)/3); ，對后三分之一進行遞回呼叫cantor(s+2*(e-s)/3,e); ，
（2）源程式1，
#include <stdio.h>
#include <string.h>
char ans[1000000];
void cantor(int s,int e)
{
if (e-s==1)
{
ans[s]='-';
return;
}
int len=(e-s)/3;
cantor(s,s+len); // 對前三分之一進行遞回
cantor(s+2*len,e); // 對后三分之一進行遞回
}
int main()
{
int i,n,len,a[13]={1};
for (i=1;i<=12;i++)
a[i]=a[i-1]*3;
while(scanf("%d",&n)!=EOF)
{
len = a[n];
memset(ans,' ',sizeof(ans)); //對整個陣列賦值為空格
cantor(0,len);
for (i=0;i<len;i++)
printf("%c",ans[i]);
printf("\n");
}
return 0;
}
也可以撰寫非遞回程式如下，
（3）源程式2，
#include <stdio.h>
#include <string.h>
char ans[13][540000];
int main()
{
int i,j,a[13]={1};
for (i=1;i<=12;i++)
a[i]=a[i-1]*3;
strcpy(ans[0],"-");
strcpy(ans[1],"- -");
for (i=2; i<=12;i++)
{
strcpy(ans[i],ans[i-1]);
int k=strlen(ans[i-1]);
for (j = 0; j<k; j++)
ans[i][j+k]=' ';
ans[i][2*k]='\0';
strcat(ans[i],ans[i-1]);
}
int n;
while (scanf("%d",&n)!=EOF)
{
printf("%s\n",ans[n]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/428437.html
標籤：C
上一篇：GCC 使用庫檔案名進行鏈接