牛客网-华为题库-删数

有一个数组 a[N] 顺序存放 0 ~ N-1 ，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以 8 个数 (N=7) 为例 :｛ 0，1，2，3，4，5，6，7 ｝，0 -> 1 -> 2 (删除) -> 3 -> 4 -> 5 (删除) -> 6 -> 7 -> 0 (删除),如此循环直到最后一个数被删除。
数据范围： 1≤n≤1000
时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M输入描述：

每组数据为一行一个整数n(小于等于1000)，为数组成员数

输出描述：

一行输出最后一个被删掉的数的原始下标位置。

示例1输入例子：

8

输出例子：

6

示例2输入例子：

1

输出例子：

0

题目解析：

约瑟夫环问题，一般形式：有序数组，长度为N，顺序存放，要求每隔M个数删除一个属，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。

迭代公式：

import sys

while True:
    try:
        num = int(input())
        dp = [0]*num
        dp[0] = 0
        for i in range(1, num):
            dp[i] = (dp[i-1] + 3) % (i+1)
        print(dp[-1])

    except:
        break

参考：

https://zhuanlan.zhihu.com/p/184955308

https://blog.csdn.net/u011500062/article/details/72855826