2014计算机学科夏令营上机考试H:Binary Tree（数学规律）

题目大意

模拟一颗二叉树，根结点为(1,1)。对任意结点(a,b)，左孩子结点为(a+b,b)，右孩子结点为(a,a+b)。
现给出一结点，判断该结点是从根结点分别向左、向右几次分支得到的。

思路分析

方法一： 逆向考虑。对于结点(a,b)，若a>b，则该结点为左孩子结点，父亲结点为(a-b,b)；否则为右孩子结点，父亲结点为(a,b-a)。则从该结点向上遍历，直至根结点(1,1)。但很不幸，这种直接了当的方法会超时。

方法二： 用除法代替减法。对于结点(a,b)，若a>b，则该结点为左孩子结点，a/b为向左分支的次数，a更新为a%b；否则该结点为右孩子结点，b/a为向右分支的次数，b更新为b%a。但此处应当注意的是，若a,b之间存在倍数关系，更新之后一方会变为0，这显然与题意不符，所以这种情况要单独考虑。只需要减少一次分支，将该值赋1即可。

代码——方法一（超时）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int a, b;
        int left = 0, right = 0;
        scanf("%d %d", &a, &b);
        while(!(a==1 && b==1))
        {
            if(a > b) // 左孩子结点
            {
                left++;
                a = a-b;
            }
            else if(a < b) // 右孩子结点
            {
                right++;
                b = b-a;
            }
        }
        printf("Scenario #%d:\n", i);
        printf("%d %d\n\n", left, right);
    }
    fclose(stdin);

    return 0;
}

代码——方法二

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
     freopen("input.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int a, b;
        int left = 0, right = 0;
        scanf("%d %d", &a, &b);
        while(!(a==1 && b==1))
        {
            if(a >= b) // 左孩子结点
            {
                if(a%b != 0)
                {
                    left += a/b;
                    a %= b;
                }
                else 
                {
                    left += a/b - 1;
                    a = 1;
                }
            }
            else // 右孩子结点
            {
                if(b%a != 0)
                {
                    right += b/a;
                    b %= a;
                }
                else 
                {
                    right += b/a - 1;
                    b = 1;
                }
            }
        }
        printf("Scenario #%d:\n", i);
        printf("%d %d\n\n", left, right);
    }
    // fclose(stdin);

    return 0;
}