捕魚知多少 ← 遞推法

【問題描述】

5人合夥夜間捕魚，上岸時都疲憊不堪，各自在湖邊的樹叢中找地方就睡覺了。清晨，第一個人醒來，将魚分成5份，把多餘的一條扔回湖中，拿自己的一份回家了；第二個人醒來，也将魚分成5份，扔掉多餘的一條魚，拿自己的一份回家了；接着，其餘3人依次醒來，也都按同樣的辦法分魚。問：5人至少共捕到多少條魚？每人醒來後看到多少條魚？

【算法分析】

假定5個人的編号分别為0，1，2，3，4，數組fish[k]表示第k個人所看到的魚數。則：

fish[0]為5個人合夥捕魚的總數

fish[1]=(fish[0]-1)*4/5

fish[2]=(fish[1]-1)*4/5

fish[3]=(fish[2]-1)*4/5

fish[4]=(fish[3]-1)*4/5

由上，推出通項表達式為：fish[i]=(fish[i-1]-1)*4/5，i=1,2,3,4

等價于 fish[i-1]=fish[i]*5/4+1，i=4,3,2,1

【算法代碼】

#include <bits/stdc++.h>
using namespace std;

int main() {
	int fish[5]= {1,1,1,1,1};
	int i=0;
	do {
		fish[4]=fish[4]+5;
		for(i=3; i>=0; i--) {
			if(fish[i+1]%4!=0) break;
			else fish[i]=fish[i+1]*5/4+1;
		}
	} while(i>=0);

	for(i=0; i<=4; i++) {
		cout<<fish[i]<<endl;
	}

	return 0;
}


/*
out:
3121
2496
1996
1596
1276
*/
           

【參考文獻】

https://blog.csdn.net/zl19890124/article/details/13293063