java - C语言算法题-韩信点兵 求解？

问题描述

完全不知道怎么下手??

问题解答

这个。。。不知道怎么说才好。。。

设共有 n 个人，三人一排，五人一排，七人一排，看最后一排剩下 a, b, c 人不就是

n % 3 = an % 5 = bn % 7 = c

下面不就很简单了么？方法 1： 暴力n 从 10 到 100 都试一下。这个不用我说了吧

方法 2： 数学方法（解同余式-初等数经）

例题：n % 3 = 2n % 5 = 4

可以转化成什么呢？

设 n / 3 = x 余 2, n / 5 = y 余 4==> 3x + 2 = 5y + 4==> 3x = 5y + 2x,y 在 自然数的最小解是 x = 4, y = 2==> n 最小是 123 和 5 的最小公倍数 = 15所以 n % 15 == 12

三个的话，先算两个，再算第三个。

#include <stdio.h>#include <stdlib.h>int met(int count, int pision, int remain) { return count % pision == remain;}int getMin(int i, int j, int k) { if (i == j && j == k) return -1; if (i >= 3) i %= 3; if (j >= 5) j %= 5; if (k >= 7) k %= 7; int count = 0; while(1) {if (count > 10) { if (met(count, 3, i) && met(count, 5, j) && met(count, 7, k)) {break; }}count++;if (count > 100) { count = -1; break;} } return count;}int main(int argc, char **args) { if (argc < 4) {printf('no enough params.'); } else {int i = atoi(args[1]);int j = atoi(args[2]);int k = atoi(args[3]);int c = getMin(i, j, k);if (c == -1) { printf('no qualified number!');} else { printf('count = %d', c);} }}