例70 國王游戲
問題描述
恰逢H國國慶，國王邀請n位大臣來玩一個有獎游戲，首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數，然后，讓這n位大臣排成一排，國王站在隊伍的最前面，排好隊后，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然后向下取整得到的結果，
國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞盡可能的少，注意，國王的位置始終在隊伍的最前面，
輸入
第一行包含一個整數n，表示大臣的人數，
第二行包含兩個整數a和b，之間用一個空格隔開，分別表示國王左手和右手上的整數，
接下來n行，每行包含兩個整數a和b，之間用一個空格隔開，分別表示每個大臣左手和右手上的整數，（1≤n≤1,000，0 < a,b < 10000）
輸出
一個整數，表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數，
輸入樣例
3
1 1
2 3
7 4
4 6
輸出樣例
2
（1）編程思路，
假設前面已經排了幾個人（包括國王），設他們左手上的數的乘積為P，
現在要給2個人排序，設第一個人左手上的數為a1，右手上的數為b1；第二個人左手上的數為a2，右手上的數為b2，
如果第一個人排在前面優于第二個人排在前面，那么有
max(S/b1,S*a1/b2) < max(S/b2,S*a2/b1)
又由于a1,b1,a2,b2,S>0，所以，S*a1/b2≥S/b2，
如果S*a1/b2 ≥ S*a2/b1，則max(S/b1,S*a1/b2)≥max(S/b2,S*a2/b1) ，與假設矛盾，
所以S*a1/b2 < S*a2/b1 ，即a1*b1 < a2*b2，
因此，需要將陣列按照大臣左右手數字的乘積a*b從小到大排序，
由于左手上的數的乘積P超出了長整數的表數范圍，所以采用高精度計算，
（2）源程式1，
#include <stdio.h>
#include <string.h>
struct Node
{
int a,b;
};
void mul(int *a,int b,int *c) // c=a*b
{
int len=a[0];
int i;
for (i=0;i<len+20;i++)
c[i]=0;
for (i=1; i<=len; i++)
{
c[i]+=(a[i]*b);
c[i+1]+=(c[i]/10);
c[i]%=10;
}
while (c[len+1]>0)
{
len++;
c[len+1]+=(c[len]/10);
c[len]%=10;
}
c[0]=len;
}
void div(int *a,int b,int *c) // c=a/b
{
int len=a[0];
int r=0; // 余數
int i;
for (i=len; i>=1; i--)
{
r=r*10+a[i];
c[i]=r/b;
r=r%b;
}
while (!c[len]) len--;
if (!len) len=1;
c[0]=len;
}
void getMax(int *x,int *y) // x=max(x,y)
{
if (y[0]<x[0]) return;
int i;
if (x[0]==y[0])
{
for (i=y[0]; i>=1; i--)
if (y[i]<x[i]) return;
else if (y[i]>x[i]) break;
}
for (i=0; i<=y[0]; i++)
x[i]=y[i];
}
int main()
{
int n;
scanf("%d",&n);
struct Node m[1005];
int i,j;
for (i=0; i<=n; i++)
scanf("%d%d",&m[i].a,&m[i].b);
for (i=1;i<n;i++)
for (j=1;j<=n-i;j++)
if (m[j].a*m[j].b>m[j+1].a*m[j+1].b)
{
struct Node tmp;
tmp=m[j]; m[j]=m[j+1]; m[j+1]=tmp;
}
int p[4100]; // 保存累乘積,p[0]保存位數，p[1]~p[p[0]]保存從低位到高位數字
int t[4100]; // 中間結果
int ans[4100]; // 最終答案
ans[0]=1;
ans[1]=0;
p[0]=1;
p[1]=1;
for (i=1; i<=n; i++)
{
mul(p,m[i-1].a,t);
for (j=0; j<=t[0]; j++) p[j]=t[j];
div(p,m[i].b,t);
getMax(ans,t);
}
for (i=ans[0]; i>=1; i--)
printf("%d",ans[i]);
printf("\n");
return 0;
}
由于題目中a和b的值不超過10000，因此可以采用萬進制進行乘法和除法的高精度運算，改寫源程式如下，
（3）源程式2，
#include <stdio.h>
#include <string.h>
#define MOD 10000
struct Node
{
int a,b;
};
void mul(int *a,int b,int *c) // c=a*b
{
int len=a[0];
int i;
for (i=0;i<len+5;i++)
c[i]=0;
for (i=1; i<=len; i++)
{
c[i]+=(a[i]*b);
c[i+1]+=(c[i]/MOD);
c[i]%=MOD;
}
while (c[len+1]>0)
{
len++;
c[len+1]+=(c[len]/MOD);
c[len]%=MOD;
}
c[0]=len;
}
void div(int *a,int b,int *c) // c=a/b
{
int len=a[0];
int r=0; // 余數
int i;
for (i=len; i>=1; i--)
{
r=r*MOD+a[i];
c[i]=r/b;
r=r%b;
}
while (!c[len]) len--;
if (!len) len=1;
c[0]=len;
}
void getMax(int *x,int *y) // x=max(x,y)
{
if (y[0]<x[0]) return;
int i;
if (x[0]==y[0])
{
for (i=y[0]; i>=1; i--)
if (y[i]<x[i]) return;
else if (y[i]>x[i]) break;
}
for (i=0; i<=y[0]; i++)
x[i]=y[i];
}
int main()
{
int n;
scanf("%d",&n);
struct Node m[1005];
int i,j;
for (i=0; i<=n; i++)
scanf("%d%d",&m[i].a,&m[i].b);
for (i=1;i<n;i++)
for (j=1;j<=n-i;j++)
if (m[j].a*m[j].b>m[j+1].a*m[j+1].b)
{
struct Node tmp;
tmp=m[j]; m[j]=m[j+1]; m[j+1]=tmp;
}
int p[1100]; // 保存累乘積，每4位1組，p[0]保存位數
int t[1100]; // 中間結果
int ans[1100]; // 最終答案
ans[0]=1;
ans[1]=0;
p[0]=1;
p[1]=1;
for (i=1; i<=n; i++)
{
mul(p,m[i-1].a,t);
for (j=0; j<=t[0]; j++) p[j]=t[j];
div(p,m[i].b,t);
getMax(ans,t);
}
printf("%d",ans[ans[0]]);
for (i=ans[0]-1; i>=1; i--)
printf("%04d",ans[i]);
printf("\n");
return 0;
}
習題70
70-1 放棋子（1）
本題選自洛谷題庫 （https://www.luogu.org/problem/P3182）
問題描述
給你一個N×N 的矩陣，每行有一個障礙，資料保證任意兩個障礙不在同一行，任意兩個障礙不在同一列，要求你在這個矩陣上放N枚棋子（障礙的位置不能放棋子），要求你放N個棋子也滿足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少種方案，
輸入
第一行一個N，接下來一個N×N 的矩陣，N≤200，0 表示沒有障礙，1 表示有障礙，
輸出
一個整數，即合法的方案數，
輸入樣例
2
0 1
1 0
輸出樣例
1
（1）編程思路，
本題是一個典型的錯排問題，
錯排問題：有n個正整數1、2、3、…、n，將這n個正整數重新排列，使其中的每一個數都不在原來的位置上，這種排列稱為正整數1、2、3、…、n的錯排，問這n個正整數的錯排種數是多少？
用遞推的方法推導錯排公式，
設將n個棋子放入矩陣中的n行（每行放一個）中，每行放的棋子與其障礙位置全不對應（均不放在障礙位置上）的方法數用D(n)表示，那么D(n-1)就表示將n-1個棋子放入n-1行中，每行放的棋子均不放在障礙位置上的方法數，
n個全部不放在障礙位置的棋子可以看成前n - 1個棋子放好后再放1個棋子，將最后1個棋子不放在障礙位置，不放在障礙位置的方式自然是與之前的棋子進行交換，交換的方式有兩種：
1）在前n-1個全部不放在障礙位置的棋子中取任意一個棋子進行交換，n-1個棋子全部不放在障礙位置的方法數為D(n-1)，在n-1個棋子中任取一個棋子的方法數為n-1，因此，這種情況下，方法數共有D(n-1)* (n-1)種，
2）在前n-1個棋子中，有n-2個棋子全部沒有放在障礙位置，有1個棋子放在了障礙位置，取放在障礙位置的這一個棋子交換，n-1個棋子中中只有一個棋子放在障礙位置的方法數有n-1，其余n-2個棋子全部沒有放在障礙位置的方法數有D(n-2)， 因此，這種情況下，方法數共有D(n-1)* (n-1)種，
由此，可得錯排的遞推公式：D(n)=[D(n-2)+D(n-1)]*(n-1) ，
初始情況為：D(1)=0 （只有1個棋子沒法放）
D(2)=1 （兩個棋子全不放在障礙位置只有1種方法）
由于n值可以為200，此時方案數超過了長整數表示的范圍，故采用高精度運算，
定義陣列int d[201][500]={0};，其中d[i][0]保存d[i]的位數len，d[i][1]~d[i][len]從低位到高位保存d[i]的各位數字，每個陣列元素保存1位數字，
（2）源程式，
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int i,j,k;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&k);
int d[201][500]={0};
d[1][0]=1; d[1][1]=0;
d[2][0]=1; d[2][1]=1;
for (k=3;k<=n;k++)
{
for (i=1;i<=d[k-1][0];i++)
{
d[k][i]=d[k-1][i]+d[k-2][i];
d[k][i]*=(k-1);
}
int len=d[k-1][0]+4;
for (i=1;i<=len;i++)
{
if (d[k][i]>=10)
{
d[k][i+1]+=d[k][i]/10;
d[k][i]=d[k][i]%10;
}
}
while (len>0 && d[k][len]==0) // 去前置0
len--;
d[k][0]=len;
}
for (i=d[n][0];i>=1;i--)
printf("%d",d[n][i]);
printf("\n");
return 0;
}
70-2 放棋子（2）
問題描述
小虎剛剛上了幼兒園，老師讓他做一個家庭作業：首先畫3行格子，第一行有3個格子，第二行有2個格子，第三行有1 個格子，每行的格子從左到右可以放棋子，但要求除第一行外，每行放的棋子數不能超過上一行的棋子，第一行的棋子數不能為0，但剩下行可以為空，玩了一會兒，小虎對哥哥大虎說：”這個作業有很多種擺放法，我想找到，但我不知道有多少種方案，你能幫助我嗎？”
大虎是學校資訊學集訓隊的，立刻想到用計算機來解決這個問題，并很快有了解答：13，
第二天他把問題拿到學校，并說如果第一行有N 個格子，第二行有N?1 個格子，……，第 N行有1 個格子，怎么辦？現在請你一塊來幫助他解決這個難題，
輸入
僅一行，一個正整數N，
輸出
一行，方案總數，
輸入樣例
2
輸出樣例
4
（1）編程思路，
設f[i][j]表示第i行放j個棋子的方案數，
顯然有 f[1][0]=1，f[1][1]=1，即第1行不放棋子和放1個棋子的方案數均為1，
F[i][0]=1，任何1行不放棋子的方法數為1，
當i=n時，
f[n][1]=f[n?1][1]+ f[n?1][0] // 第n行放1個棋子可看成第n-1行放1個棋子或不放棋子而得來
f[n][2]= f[n?1][0]+ f[n?1][1]+f[n?1][2] =f[n][1]+f[n-1][2]
……
f[n][k]= f[n?1][0]+f[n?1][1]+f[n?1][2]+?+f[n?1][k?1]+f[n-1][k]= f[n][k?1]+f[n?1][k]
即遞推公式為：f[n][k] = f[n][k?1]+f[n?1][k] （0≤k≤n）
計算出所有的f[n][k]后，將f[n][1]~f[n][n]的值累加起來，就是n行放棋子的總方案數，
由于n值可以為100，此時方案數超過了長整數表示的范圍，故采用高精度運算，
定義陣列int f[101][101][61]={0};，其中f[i][j][0]保存f[i][j]的位數len，f[i][j][1]~f[i][j][len]從低位到高位保存f[i][j]的數字，每個元素保存1位數字，
（2）源程式1，
#include <stdio.h>
int max(int a,int b)
{
return a>b?a:b;
}
int f[101][101][61]={0};
int main()
{
int n;
scanf("%d",&n);
int i,j,k;
f[1][0][0]=1;
f[1][0][1]=1;
f[1][1][0]=1;
f[1][1][1]=1;
for (i=2;i<=n;i++)
{
f[i][0][0]=1;
f[i][0][1]=1;
for (j=1;j<=i;j++)
{
int len=max(f[i][j-1][0],f[i-1][j][0]);
int cf=0;
for (k=1;k<=len;k++)
{
f[i][j][k]=f[i][j-1][k]+f[i-1][j][k]+cf;
cf=f[i][j][k]/10;
f[i][j][k]=f[i][j][k]%10;
}
while (cf!=0)
{
f[i][j][++len]=cf%10;
cf/=10;
}
f[i][j][0]=len;
}
}
int ans[61]={0};
ans[0]=1;
ans[1]=0;
for (i=1;i<=n;i++)
{
int len=max(ans[0],f[n][i][0]);
int cf=0;
for (k=1;k<=len;k++)
{
ans[k]=f[n][i][k]+ans[k]+cf;
cf=ans[k]/10;
ans[k]=ans[k]%10;
}
while (cf!=0)
{
ans[++len]=cf%10;
cf/=10;
}
ans[0]=len;
}
for (i=ans[0];i>=1;i--)
printf("%d",ans[i]);
printf("\n");
return 0;
}
由于題目中進行的是大整數加法，故一個陣列元素可以保存9位數字，這樣進行高精度加法運算，既可以節省空間，也可以加快運算速度，改寫源程式如下，
（3）源程式2，
#include <stdio.h>
#define MOD 1000000000
int max(int a,int b)
{
return a>b?a:b;
}
int f[101][101][8]={0};
int main()
{
int n;
scanf("%d",&n);
int i,j,k;
f[1][0][0]=1;
f[1][0][1]=1;
f[1][1][0]=1;
f[1][1][1]=1;
for (i=2;i<=n;i++)
{
f[i][0][0]=1;
f[i][0][1]=1;
for (j=1;j<=i;j++)
{
int len=max(f[i][j-1][0],f[i-1][j][0]);
int cf=0;
for (k=1;k<=len;k++)
{
f[i][j][k]=f[i][j-1][k]+f[i-1][j][k]+cf;
cf=f[i][j][k]/MOD;
f[i][j][k]=f[i][j][k]%MOD;
}
if (cf!=0)
f[i][j][++len]=cf;
f[i][j][0]=len;
}
}
int ans[8]={0};
ans[0]=1;
ans[1]=0;
for (i=1;i<=n;i++)
{
int len=max(ans[0],f[n][i][0]);
int cf=0;
for (k=1;k<=len;k++)
{
ans[k]=f[n][i][k]+ans[k]+cf;
cf=ans[k]/MOD;
ans[k]=ans[k]%MOD;
}
if (cf!=0)
ans[++len]=cf;
ans[0]=len;
}
printf("%d",ans[ans[0]]);
for (i=ans[0]-1;i>=1;i--)
printf("%09d",ans[i]);
printf("\n");
return 0;
}
70-3 三只小豬
問題描述
有三只小豬為了自己的安全，合伙建造了兩個新磚房，怎樣把三個小豬分配到兩個房子里呢？第三只小豬是三只小豬中最聰明的一只，為了不浪費任何一個房子，它總共考慮了三種方案：
1）第1只小豬和第2只小豬同住一間，第3只小豬獨自住一間；
2）第1只小豬和第3只小豬同住一間，第2只小豬獨自住一間；
3）第2只小豬和第3只小豬同住一間，第1只小豬獨自住一間，
“但是將來怎么辦呢？”第三只小豬知道將來隨著成員的增多，它們將會蓋更多的房子，它想知道給定了房子和豬的數目后，房子的分配方案有多少？
輸入
輸入一行，包含兩個整數n和m，分別表示小豬的數目和房間數（1≤n≤50，0≤m≤50），
輸出
輸出一個整數，表示將n只小豬安置在m個房間且沒有房間空閑的方案數，
輸入樣例
4 2
輸出樣例
7
（1）編程思路，
設f[n][m]表示n只小豬安置進m個房子里的方案數，
對于第n只小豬，有兩種安排方法：1）該小豬獨自住一個房間，則其他n-1只小豬安置進m-1個房子，方案數有f[n-1][m-1]；2）該小豬在m個房間中選1間和其它的小豬合住，方案數有m*f[n-1][m]，
由此可得：f[n][m]=f[n-1][m-1]+m*f[n-1][m]
初始時，f[1][1]=1 ，
由于資料范圍較大，需要使用高精加和高精乘，由此每個元素f[i][j]用一個一維陣串列示，可以定義為陣列f[i][j][k]，其中f[i][j][0]表示f[i][j]的位數，之后的f[i][j][1]~f[i][j][k] 表示從低位到高位的每一位，
（2）源程式，
#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
if (n<m || m==0)
printf("0\n");
else
{
int f[55][55][61];
memset(f,0,sizeof(f));
int i,j,k;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
if (i<j)
{
f[i][j][0]=1; f[i][j][1]=0;
}
else if (i==j)
{
f[i][j][0]=1; f[i][j][1]=1;
}
else
{
// f[n][m]=f[n-1][m-1]+m*f[n-1][m]
int len=max(f[i-1][j-1][0],f[i-1][j][0]);
for (k=1;k<=f[i-1][j][0];k++)
f[i][j][k]=j*f[i-1][j][k];
int cf=0;
for (k=1;k<=len;k++)
{
f[i][j][k]+=f[i-1][j-1][k]+cf;
cf=f[i][j][k]/10;
f[i][j][k]=f[i][j][k]%10;
}
while (cf!=0)
{
f[i][j][++len]=cf%10;
cf/=10;
}
f[i][j][0]=len;
}
}
}
for (i=f[n][m][0];i>=1;i--)
printf("%d",f[n][m][i]);
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/429251.html
標籤：其他