递归训练·农场周围的道路
题目描述
John的奶牛对探索农场周围的地域很感兴趣。最初，所有N头奶牛沿着一条路一起行动。在遇到一个岔路口后，奶牛们分成两组（没有一组为空）后继续往下走。当其中的一组遇到另一个岔路口后，继续分成两组，一直这样下去。
奶牛有一种奇特的分组方法：如果它们能将奶牛分成两组奶牛数目相差K，则它们将按此方法分组；否则，它们将停止探索，开始安静地吃草。
假定在路上总是会有新的岔路出行，计算最后停下来吃草的奶牛的组数
输入
一行两个用一个空格隔开的整数N和K，1<=N<=1000000000
输出
一行一个整数，表示最后停下来吃草的奶牛组数
样例输入
6 2
样例输出
3
我的看法：
找找规律再递归，分两条路走，如果是奇数则停，sum++，不是则继续递归。
c++代码
#include<bits/stdc++.h>using namespace std;int sum=0;void johncow(int n,int t){ int k=n-t; if(k&1||k<1) { sum++; return ; } johncow(k/2,t); johncow(t+k/2,t);}int main(){ int n,t; scanf("%d %d",&n,&t); johncow(n,t); printf("%d",sum); return 0;}