uva 10940 - Throwing cards away II

逃离我推掉我的手 2022-05-12 23:16 233阅读 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 条评论，233人围观）

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

相关阅读

    相关 throw 和throws 关键字

    1.系统自动抛出异常： 当程序中有逻辑错误、类型转换错误时，系统自动抛出异常，例如： ![70][] ![70 1][]  2 .throw 关键字抛出异常 ![

    男娘i男娘i/ 0 赞/ 286 阅读