uva 10940 - Throwing cards away II

 

题目大意：给出n，表示有n张牌，按照1~n的顺序排列，每次取出顶部的两张牌，第一张丢掉，第二张放到牌堆的最底部，问最后剩下的那张牌是多少。

 

解题思路：可能我的思路有点难理解，我不是通过打表找规律去推公式， 而是模拟了人的思维去处理这个牌的问题，首先第一次为n张牌，第一遍丢牌肯定是奇数牌，所以可以将所有的偶数留下，标号均可以模2，问题转换成1~n/2张牌的问题。

其次，每一次划分子问题的时候，当前次丢掉奇数牌还是偶数牌和上一轮丢掉奇数牌还是偶数牌以及牌的数量有关。

然后处理好递归返回值的公式就可以了。

 

算法复杂度为o(logn)。

 

 

#include <stdio.h>  
  
int solve (int n, int flag) {  
    int tmp = (n + flag) % 2;  
    if (n == 1) return 1;  
    if (flag) {  
        return solve((n + 1) / 2, tmp) * 2 - 1;  
    } else {  
        return solve(n / 2, tmp) * 2;  
    }  
}  
  
int main () {  
    int n;  
    while (scanf("%d", &n), n) {  
        printf("%d\n", solve(n, 0));  
    }     
    return 0;  
}  

 

补充：软件开发 , C++ ,