uva 10940 - Throwing cards away II

逃离我推掉我的手 2022-05-12 23:16 243阅读 0赞

题目链接：uva 10940 - Throwing cards away

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

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

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

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

算法复杂度为o(logn)。

  1. #include <stdio.h>
  3. int solve (int n, int flag) {
  4.     int tmp = (n + flag) % 2;
  5.     if (n == 1) return 1;
  6.     if (flag) {
  7.         return solve((n + 1) / 2, tmp) * 2 - 1;
  8.     } else {
  9.         return solve(n / 2, tmp) * 2;
  10.     }
  11. }
  13. int main () {
  14.     int n;
  15.     while (scanf("%d", &n), n) {
  16.         printf("%d\n", solve(n, 0));
  17.     }    
  18.     return 0;
  19. }

发表评论

表情：
评论列表 （有 0 条评论，243人围观）

还没有评论，来说两句吧...

相关阅读

    相关 UVA 12298 Super Poker II（FFT）

    题意： 每个花色恰好选择一张牌 能够构成点数和大小为N的方案数 用类似生成函数的想法，多项式的幂值表示大小，前面的系数表示的是方案数 因此想到了多项式乘法，用F

    心已赠人心已赠人/ 0 赞/ 2 阅读