题目链接:https://buaacoding.cn/problem/1971/index
写在前面:
相信有C语言基础的同学都不难理解递归。举个简单的例子:从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山...
递归是我们经常用到的算法,当熟悉递归的做法以及题目的思路时,递归经常可以简化代码量。当然,递归也有他的弊端,那就是递归是一个不断深入的过程,在这过程中它每次都需要开辟一块栈空间来存储,使得递归的运行效率通常较低。当然,理论上,每个递归算法都可以转化为非递归(循环)来实现。
题目分析:在每一轮当中,每个人告诉他要告诉的人他知道的真心话(好拗口)。
注意:在这一轮结束后,大家同时知道新的真心话。因为我在看有的代码时发现有同学用循环实现时通常会为大家知道真心话添加顺序,即在同一轮中,如果一个人知道新的真心话后,他接下来也会把这个真心话告诉他要告诉的人,但这其实是不对的。
递归,看程序即可。
#include<stdio.h> #define MAX 1005 #define max(a,b) (a>b?a:b) int n, pass[MAX]; // pass数组用来存储他要告诉真心话的人 int fun(int x) { if(x == n) return 0; return 1 + fun(pass[x]); } int main() { int ans = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &pass[i]); for(int i = 1; i < n; i++) ans = max(ans, fun(i)); printf("%d", ans); return 0; }
写在后面:以上代码均非本人所想,来源于参考大佬思路。希望可以和大家一起交流学习,共同进步!
原文:https://www.cnblogs.com/flying-rabbit/p/10721058.html