例46 巧妙稱重
題目描述
有N個籃子，編號1~N，籃子中有很多金幣，每個重w，但是有一個編號的籃子中，每個金幣重d，現從第一個籃子中拿1個金幣，第二個籃子中拿2個，…，第N-1中拿N-1個，第N中不拿，給出這些金幣的總重量wei，問：是第幾個籃子中的金幣重量較輕？
輸入格式
輸入檔案將由一行或多行組成；每行包含四個正整數，由一個空格分隔，前三個整數分別是數字N、w和d，如上所述，第四個整數是所選硬幣稱重的結果，
N至少為2，但不超過8000，w的值最多為30，d的值將小于w，
輸出格式
對于每組測驗資料輸出一行，由一個正整陣列成：裝有比其他籃子中金幣輕的金幣的籃子編號，
輸入樣例
10 25 8 1109
10 25 8 1045
8000 30 12 959879400
輸出樣例
2
10
50
（1）編程思路，
這是一道數學題分析題，若設1~N-1這N-1個籃子中放的金幣均為重量為w的金幣，則應有的總重量為：w*（1+n-1)*(n-1)/2（簡單的等引數列求和），所求的和減去實際稱出的重量wei，得到金幣重量的差值sum = ((n-1)*(n-1+1)/2)*w-wei，若sum為0，則裝有重量為d的籃子編號必為N；若sum不為0，除以d，得到較輕金幣的個數，即為所求編號，
（2）源程式，
#include <stdio.h>
int main()
{
int n,w,d,p;
while (scanf("%d%d%d%d",&n,&w,&d,&p)!=EOF)
{
int sum = ((n-1)*(n-1+1)/2)*w-p;
if(sum==0)
printf("%d\n",n);
else
printf("%d\n",sum/d);
}
return 0;
}
習題46
46-1 鬼谷子的錢袋
本題選自洛谷題庫 （https://www.luogu.org/problem/P2320）
題目描述
鬼谷子非常聰明，正因為這樣，他非常繁忙，經常有各諸侯車的特派員前來向他咨詢時政，
有一天，他在咸陽游歷的時候，朋友告訴他在咸陽最大的拍賣行（聚寶商行）將要舉行一場拍賣會，其中有一件寶物引起了他極大的興趣，那就是無字天書，
但是，他的行程安排得很滿，他已經買好了去邯鄲的長途馬車票，不巧的是出發時間是在拍賣會快要結束的時候，于是，他決定事先做好準備，將自己的金幣數好并用一個個的小錢袋裝好，以便在他現有金幣的支付能力下，任何數目的金幣他都能用這些封閉好的小錢的組合來付賬，
鬼谷子也是一個非常節儉的人，他想方設法使自己在滿足上述要求的前提下，所用的錢袋數最少，并且沒有兩個錢袋裝有相同的大于1的金幣數，假設他有m個金幣，你能猜到他會用多少個錢袋，并且每個錢袋裝多少個金幣嗎？
輸入格式
包含一個整數，表示鬼谷子現有的總的金幣數目m，其中，1≤m ≤1000000000，
輸出格式
兩行，第一行一個整數h，表示所用錢袋個數
第二行表示每個錢袋所裝的金幣個數，由小到大輸出，空格隔開
輸入樣例
3
輸出樣例
2
1 2
（1）編程思路，
先看看金幣數目m為1~10怎么表示，
m=1，顯然1個錢袋，裝1個金幣；m=2，用2個錢袋，各裝1個金幣；
m=3，用2個錢袋，分別裝1個和2個金幣；
m=4，用3個錢袋，分別裝1個、1個和2個金幣；
m=5，用3個錢袋，分別裝1個、1個和3個金幣；
m=6，用3個錢袋，分別裝1個、2個和3個金幣；
m=7，用3個錢袋，分別裝1個、2個和4個金幣；
m=8，用4個錢袋，分別裝1個、1個、2個和4個金幣；
m=9，用4個錢袋，分別裝1個、1個、2個和5個金幣；
m=10，用4個錢袋，分別裝1個、1個、3個和5個金幣；
……
由上面規律可以看出，n以內的任何數字可以用1到n/2以內的數字表示，n/2以內的任何數字可以用1到n/4以內的數字表示，……，
例如，為了表示15，一個袋子裝（15+1）/2=8個金幣，剩下7個金幣；為了表示7，用一個袋子裝（7+1）/2=4個金幣，剩下3個金幣；為了表示3，用一個袋子裝(3+1)/2=2個金幣，剩下2個金幣，可用兩個袋子，各裝1個金幣，即m=15，用4個錢袋，分別裝1個、2個、4個金幣和8個金幣；
M=29時，一個袋子裝(29+1)/2=15個金幣，剩下14個金幣用4個袋子，分別裝1個、2個、4個金幣和7個金幣，
M=30時，一個袋子裝(30+1)/2=15個金幣，剩下15個金幣用4個袋子，分別裝1個、2個、4個金幣和8個金幣，
M=31時，一個袋子裝(31+1)/2=16個金幣，剩下15個金幣用4個袋子，分別裝1個、2個、4個金幣和8個金幣，
……
（2）源程式，
#include <stdio.h>
int main()
{
int a[32];
int n;
scanf("%d",&n);
int cnt=0;
while (n>0)
{
a[cnt++]=(n+1)/2;
n=n/2;
}
printf("%d\n",cnt);
for (int i=cnt-1;i>=0;i--)
printf("%d ",a[i]);
printf("\n");
return 0;
}
46-2 圓桌會議
題目描述
N個哲學家圍坐在一張圓形的桌子旁進行交流，在一天在討論的時候，哲學家Eddy想出了一個極為古怪的想法，如果他們在每一分鐘內，一對相鄰的兩個哲學家交換一下位子，那么要多少時間才能得到與原始狀態相反的座位順序呢?
輸入格式
對于給定數目N（1<=N<=32767），表示有N個哲學家，求要多少時間才能得到與原始狀態相反的座位順序，即對于每個人，原先在他左邊的人后來在他右邊，原先在他右邊的人在他左邊，
輸出格式
對每個資料輸出一行，表示需要的時間（以分鐘為單位），
輸入樣例
4
5
6
輸出樣例
2
4
6
（1）編程思路，
若n個哲學家坐成一排，123…n逆序變為n…321，需要交換位置1+2+…+(n-1)=n*(n-1)/2次，即1右移n-1步，2右移n-2步，……，
現在n個哲學家在圓桌邊圍成一圈，所以可以雙向移動，因而可將n分成兩部分，n/2和n-n/2，兩部分分別按一排獨自逆序，可以達到時間最少，
例如1234，可分成12和34，2分鐘后可得到2143，由于成圈，所以也是逆序，
再如12345，可分成123和45，123逆序為321用2分鐘，45逆序為54用1分鐘，3分鐘后可得到32154，由于成圈，所以也是逆序，
（2）源程式，
#include <stdio.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int a=n/2;
int b=n-a;
printf("%d\n",a*(a-1)/2+b*(b-1)/2);
}
return 0;
}
46-3 取木棍
題目描述
有邊長分別為1~n的n根小木棍，現在要求拿走盡量少的小木棍，使得剩下的小木棍任意取三根都不能組成三角形，
輸入格式
輸入第一行包含一個整數T（T≤20），表示測驗用例的數量，
對于每個測驗用例，只有一行描述給定的整數n（1≤N≤20），
輸出格式
對于每個測驗用例，輸出一行“case#x:y”，其中x是用例編號（從1開始），y是應取走的最小木棍數目，
輸入樣例
3
4
5
6
輸出樣例
Case #1: 1
Case #2: 1
Case #3: 2
（1）編程思路，
邊長為1~n的n根小木棍取走一些后，若最后剩下的小木棍的邊長構成Fib（斐波那契）數列，則一定可以保證任意三根木棍都不能組成三角形，
（2）源程式，
#include <stdio.h>
int main()
{
int a[22]={0};
a[1]=a[2]=a[3]=a[5]=a[8]=a[13]=a[21]=1;
int i;
for (i=2;i<22;i++)
a[i]+=a[i-1];
int t;
scanf("%d",&t);
for (i=1; i<=t; i++){
int n;
scanf("%d",&n);
printf("Case #%d: %d\n", i,n-a[n]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412840.html
標籤：C
上一篇：吃頓外賣的時間帶你解決單鏈表問題