高埗做网站公司,shopee怎么注册开店,昆明网站建设贴吧,徐州公司网站制作文章目录问题描述思路代码实现问题描述
有 1~N 个数字#xff0c;从 1~m 依次报数#xff0c;数到 m 的数字要被删掉#xff0c;求最后剩下的数字是#xff1f; 思路
第一次报数第二次报数1n-m12n-m2……m-2n-2m-1n-1m被删掉了m11m22……n-1n-1-mnn-m
通过上面的表格从 1~m 依次报数数到 m 的数字要被删掉求最后剩下的数字是 思路
第一次报数第二次报数1n-m12n-m2……m-2n-2m-1n-1m被删掉了m11m22……n-1n-1-mnn-m
通过上面的表格我们可以发现这样的规律
将某数字第一次报数设为 first 第二次报数设为 second 。那么存在这样的关系first(secondm−1)%n1first (second m - 1) \% n 1first(secondm−1)%n1公式一
为什么不是 first(secondm)%nfirst (second m) \% nfirst(secondm)%n 公式二呢其实一开始我确实总结出来的是公式二但是发现有个漏洞数字编号是从 1 开始的而公式二的编号是从 0 开始的具体来说就是当 second n-m 时first 0 。可以看到并不符合实际firstn 才对。换言之也就是如果我们从 0 开始计数那么公式二是可用的如何从 0 开始计数呢 答案就是把数字序列存到数组里嘛~
因此将公式二可以进化为 first(secondm)%n1first (second m) \% n 1first(secondm)%n1公式三但是简单的为公式二的结果 1 就导致在公式二中本来只有 second n-m 结果不符合实际而在公式三中变成了只有 second n-m 的结果符合实际原本没问题的都变得有问题了……这是因为我们没有做到加减均衡只有 1而没有 -1 。因此公式一应运而生~
那么我们可以得到这样的规律
当n1时f(n)(f(n−1)m−1)%n1当 n1 时f(n) (f(n-1) m - 1) \% n 1当n1时f(n)(f(n−1)m−1)%n1 当n1时f(1)1当 n1 时f(1) 1当n1时f(1)1
解释一下就是剩最后一个数的时候直接返回最后一次报数为 1 的数反之则需要继续删除一个数。
而当 n-11 时f(n) 也就意味着最后一次报数为 1 的数倒数第二次报数的时候它报的是几。
那么对于 f(n-1) 的调用也就意味着本次报数为 n 的数下一次报数为几。
说到这里已经很清楚了显而易见的递归思想。 代码实现
int m;
int yuesefu(int n){if(n 1) return 1; // 最后一次报数为 1开始回溯return (yuesefu(n-1) m - 1) % n 1; // f(n-1)1的时候开始回溯求最后一次报数为 1 的数第一次报数为几
}// 还可以再简化
int m;
int yuesefu(int n){return n 1 ? 1 : (yuesefu(n-1) m - 1) % n 1;
}// 如果将数字序列存入数组中则可用公式二
int m;
int yuesefu(int n){return n 0 ? 0 : (yuesefu(n-1) m) % n;
}
