方法二(递归算法)#import <Foundation/Foundation.h>
int sub(int n); //int getNumber(int n); //int number; int main(int argc, const char * argv[]) { @autoreleasepool { // // insert code here... // NSLog(@"Hello, World!"); // number = getNumber(5); // NSLog(@"%i",number); int number; number = sub(5); NSLog(@"%i",number); }
return 0;
}
int sub(int n) { if(n == 1) { static int i = 0; do { i++; } while (i % 5 != 0); return (i + 1); //5人平分后多出一条鱼 }else { int t; do { t = sub(n - 1); } while (t % 4 != 0); return (t / 4 * 5+1); } }
分析: 输入5是想求倒数第五个人拿之前有多少鱼。 n = 5,一直往前递归,n = 4,n=3,n=2。。。 当n=2时,就时倒数第二个人(第四人)拿鱼的时候,有多少鱼。 那么,由题目可以知道,倒数第二个人拿鱼时,剩余的鱼应该也能满足减去1后能被5整除。 又由于,倒数第三人取过鱼后,剩余的鱼数一定能被4整除。所以,也要满足这个条件。 从而,sub(5)往下递归到sub(2),再递归sub(1),算出sub(2)之后再回溯给sub(3),sub(4),sub(5)看看是否依次能够满足条件,不满足就继续 i++ , 知道满足sub(5),往下的所有都满足,就得到了要求的数。就可以得到sub(5)。
废死个脑筋,吃饭去了,想的头晕。
|