|
锁定老帖子 主题：一道算法题看程序员的魅力
该帖已经被评为隐藏帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-07-10
思路有问题。
如果3个人一桌，多2个人。 如果5个人一桌，多4个人。 如果7个人一桌，多6个人。 如果9个人一桌，多8个人。 如果我设置总人数为(n-1),那么n肯定是可以被3.5.7.9整除？那么这个就好做了吧？即所有解应该为n*(3*5*7*9-1) |
| 返回顶楼 | |
|
发表时间：2011-07-11
楼主十分蛋疼。。无语了。。
|
| 返回顶楼 | |
|
发表时间：2011-07-11
楼主好棒，真的好棒...神一般的存在
|
| 返回顶楼 | |
|
发表时间：2011-07-11
lyqiang 写道 zcb11051 写道 gbfd2012 写道 为什么列个2元方程组，没有解呢。。。。。。。。
3x+2=y; 11x=y; 谁能告诉我为什么。。。 这个没整数解，是1/4了~~~ 我也想知道这方程组怎么会错，x是所有桌子，y是所有人数。 3个人一张桌子，还剩两个人，就应该是3x+2=y; 11个人一张桌子刚好，就应该是11x=y; 哪里错了呢？ ------------------------- 3人一桌时的总桌数 n 与11人一桌时的总桌数 m 是不等的 |
| 返回顶楼 | |
|
发表时间：2011-07-11
mindfocus 写道 人数设为n
条件1， (n+1) % 3 = 0; 条件2， (n+1) % 5 = 0; 条件3, (n+1) % 7 = 0; 条件4， (n+1) % 9 = 0; 条件5, n%11 = 0; 条件1是多余的。 条件2、3、4，可得出， n+1 = 315m（m为自然数）, 上述等式结合条件5，可得出 (315m-1) % 11 = 0。
public class Main{
public static void main(String[] args) {
int m = gcf(gcf(gcf(3, 5),7),9);
int n;
for (int k = 1; ; k++) {
if ((m*k-1)%11 == 0) {
n = m * k - 1;
break;
}
}
System.out.println(n);
}
// 最大公约数
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
// 最大公倍数
public static int gcf(int a, int b) {
return a * b / gcd(a, b);
}
}
相比较起来，还是穷举法直接、易懂。 我也这思路 |
| 返回顶楼 | |
|
发表时间：2011-07-13
pwc_pengwenchao 写道 lyqiang 写道 zcb11051 写道 gbfd2012 写道 为什么列个2元方程组，没有解呢。。。。。。。。
3x+2=y; 11x=y; 谁能告诉我为什么。。。 这个没整数解，是1/4了~~~ 我也想知道这方程组怎么会错，x是所有桌子，y是所有人数。 3个人一张桌子，还剩两个人，就应该是3x+2=y; 11个人一张桌子刚好，就应该是11x=y; 哪里错了呢？ 谁告诉你 3x+2=y 和 11x=y 这两个y是相等的？ 这两个y的确相等，只是x却不是同一个x了…… |
| 返回顶楼 | |
|
发表时间：2011-07-13
疯了。。。。
|
| 返回顶楼 | |
|
发表时间：2011-07-14
最后修改：2011-07-14
不知楼主想说什么，枚举算法是个人就能想到。记得大学学组合数学时做这种题太多了，应用中国剩余定理求同余方程。
|
| 返回顶楼 | |
|
发表时间：2011-07-14
gbfd2012 写道 为什么列个2元方程组，没有解呢。。。。。。。。
3x+2=y; 11x=y; 谁能告诉我为什么。。。 当按3人和11人分的时候桌数是不一样的，所以你这个两个y应该是y1和y2 |
| 返回顶楼 | |
|
发表时间：2011-07-14
最后修改：2011-07-14
说下我的想法:
a. 从最后一个条件看出总人数是11的倍数。 b. 从前面4个条件看出，如果再加一个人都能被3，5，7，9整除，也就是说总人数加1是3，5，7，9的最小公倍数315的整数倍。 所以 11×X+1=315Y(X,Y均为自然数） 315的整数倍尾数只能为0和5，所以11×X的尾数只能为9和4，只需要找给定范围内的尾数为4和9的自然数乘以11，再加1，如果得到的结果是315的整数倍，那么11×X就是总人数. |
| 返回顶楼 | |
