[全民编程]76道高难度C++练习题.含NOI竞赛题.欢迎挑战(页 2) - C++论坛 - C++教室

HCL 发表于 2007-6-17 10:32

第五题那个我是用VC6.0写的,对于正整数都可以,没有考虑其他的![em01]

HCL 发表于 2007-6-17 10:33

希望此贴可以长期存在,并把已经完成的题放在楼顶作个标记嘛~谢谢![em02]

aipb2007 发表于 2007-6-17 10:42

放了！呵呵~~~~~~~~

simonray 发表于 2007-6-17 11:08

新手...有点看不懂.

aipb2007 发表于 2007-6-17 11:19

大家讨论下16题最少称几次啊？ ------------------------------------------------------------------ 16. 设有８枚硬币ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，其中有一枚硬币是伪造的。 真伪硬币的区别仅是重量不同，可能重，可能轻。今要求以天平为工具，用最少的 比较次数挑出伪造硬币，并鉴定它是重还是轻。 ------------------------------------------------------------------ 我用4次似乎多了！

HCL 发表于 2007-6-17 12:55

仿佛是第六题吧!帮忙看一下,如果有冗余的地方还望多提点一下[em01] 希望看起不会太痛苦! --VC6.0 #include <iostream> #include <iomanip> #include <vector>
using namespace std;
int main() { cout <<"Enter a number : "; int number; cin >>number; int total = number * number; int i = 0; int j = 0; //(1): for (i = 0 ; i < number ; ++i) { for (j = 0 ; j < number ; ++j) { cout <<setw(5)<<total; total -= 1; } cout <<endl; } cout <<endl;
 //(2) i = 0; j = 0; int num = 1; vector< vector<int> > a; a.resize(number); for (int x = 0; x < number; ++x) a[x].resize(number); while(num <= number * number) { if(i == 0 || j == number) { if(j == number){ i+=1; j--; } for(; j >= 0 && i != number; --j){ a[i][j] = num; num++; i++; } ++j; } else if (j == 0 || i == number) { if (i == number){ j+=1; i--; } for(; i >= 0 && j != number; --i){ a[i][j] = num; num++; j++; } ++i; } } for ( i = 0 ; i < number ; ++i) { for (int j = 0 ; j < number ; ++j) cout <<setw(5)<<a[i][j]; cout <<endl; } cout <<endl;

HCL 发表于 2007-6-17 12:55

//(3) i = 0; j = 0; num = 0; vector< vector<int> > b; b.resize(number); for (int y = 0; y < number; ++y) b[y].resize(number); int temp1 = 0; int temp2 = number - 1; for (int t = 0; t <= number/2; t++, temp1++,temp2--,++i,++j) { for(i = temp1; i < temp2; i++) b[i][j] = ++num; for(j = temp1; j < temp2; j++) b[i][j] = ++num; for(i = temp2; i > temp1; i--) b[i][j] = ++num; for(j = temp2; j > temp1; j--) b[i][j] = ++num; if(temp1 == temp2) b[temp1][temp2] = ++num; }
 for ( i = 0 ; i < number ; ++i) { for (int j = 0 ; j < number ; ++j) cout <<setw(5)<<b[i][j]; cout <<endl; } cout <<endl; return 0; }

HCL 发表于 2007-6-17 13:01

16题应该可以用二分法吧!

jiaju111 发表于 2007-6-17 13:29

<DIV class=quote>以下是引用aipb2007在2007-6-17 11:19:51的发言： 大家讨论下16题最少称几次啊？ ------------------------------------------------------------------ 16. 设有８枚硬币ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，其中有一枚硬币是伪造的。 真伪硬币的区别仅是重量不同，可能重，可能轻。今要求以天平为工具，用最少的 比较次数挑出伪造硬币，并鉴定它是重还是轻。 ------------------------------------------------------------------ 我用4次似乎多了！</DIV>
3次就够了吧 第一次 a,b,c 对 d,e,f 若平衡……（简单） 若不平衡（如果左边重）（如果右边重同样道理，因为题目是对称的） 第二次 b,c,d对e,f,g 若平衡则a偏重，问题解决 若不平衡（如果仍然是左边重）则是b,或c偏重,再称一次就解决了 （如果是左边轻）则是d偏轻，问题解决

aipb2007 发表于 2007-6-17 14:11

HCL 发表于 2007-6-17 14:48

厉害啊~佩服!

野比发表于 2007-6-17 16:17

<DIV class=quote>以下是引用jiaju111在2007-6-17 13:29:09的发言： 
3次就够了吧 第一次 a,b,c 对 d,e,f 若平衡……（简单） 若不平衡（如果左边重）（如果右边重同样道理，因为题目是对称的） 第二次 b,c,d对e,f,g 若平衡则a偏重，问题解决 若不平衡（如果仍然是左边重）则是b,或c偏重,再称一次就解决了 （如果是左边轻）则是d偏轻，问题解决 </DIV>
好像有些不对劲.. 这里"若不平衡（如果仍然是左边重）则是b,或c偏重 / (如果是左边轻)则是d偏轻", 没有考虑到"e或f偏轻"的情况... 因为不能保证一定会把偏轻的那一个当成d拿到左边去(三选一)...所以分析时思路就被误导在"问题一定出在左边"上了. 之后再称已经没有意义了. 我个人认为, 3次只能找出假币, 要判断轻重必须称第4次. 假币判断方法: 1.左右各放2个, 平衡:剩下4个有假币; 不平衡:这4个有假币 2.在有假币的4个中, 取2个放上天平称, 平衡: 假币在剩下2个中; 不平衡:假币在这2个中 此时: 可以确定出A组:2个, 有假币; B组: 6个, 全部标准. 3.从A组取1个(标记A1), 和B组取1个标准硬币放到天平上比较. 平衡: 则A2为假币; 不平衡: A1为假币. 4.将假币与标准硬币做最后比较, 确定轻重.

jiaju111 发表于 2007-6-17 17:10

<DIV class=quote>以下是引用野比在2007-6-17 16:17:55的发言： 
好像有些不对劲.. 这里"若不平衡（如果仍然是左边重）则是b,或c偏重 / (如果是左边轻)则是d偏轻", 没有考虑到"e或f偏轻"的情况... 因为不能保证一定会把偏轻的那一个当成d拿到左边去(三选一)...所以分析时思路就被误导在"问题一定出在左边"上了. 之后再称已经没有意义了. 我个人认为, 3次只能找出假币, 要判断轻重必须称第4次. 假币判断方法: 1.左右各放2个, 平衡:剩下4个有假币; 不平衡:这4个有假币 2.在有假币的4个中, 取2个放上天平称, 平衡: 假币在剩下2个中; 不平衡:假币在这2个中 此时: 可以确定出A组:2个, 有假币; B组: 6个, 全部标准. 3.从A组取1个(标记A1), 和B组取1个标准硬币放到天平上比较. 平衡: 则A2为假币; 不平衡: A1为假币. 4.将假币与标准硬币做最后比较, 确定轻重.</DIV>
多谢指正啊，呵呵，不好意思！ 不过我觉得还是可以只用3次：
第一次 a,b,c 对 d,e,f 若平衡……（简单）
若不平衡（如果左边重）（如果右边重同样道理，因为题目是对称的）
第二次 c,d,e 对f,g,h
若平衡则a或b偏重，再称一次解决
若不平衡（如果仍然是左边重）则是c偏重或者f偏轻，再称一次解决 （如果是左边轻）则是d或e偏轻，再称一次解决

野比发表于 2007-6-17 17:49

恩. 受启发了. 我发现我的方法可以改进.. 也只需要3次了! 假币判断方法: 1.左右各放2个, 平衡:剩下4个有假币; 不平衡:这4个有假币 2.在有假币的4个中, 取较[COLOR=BLUE]重[/COLOR]的2个放上天平称, 平衡: 假币在剩下2个中, 且较[COLOR=BLUE]轻[/COLOR]; 不平衡:假币在这2个中, 且较[COLOR=BLUE]重[/COLOR] 此时: 可以确定出A组:2个, 有假币; B组: 6个, 全部标准. 3.从A组取1个(标记A1), 和B组取1个标准硬币放到天平上比较. 平衡: 则A2为假币; 不平衡: A1为假币. [COLOR=BLUE]假币轻重已由第2步得出[/COLOR]

jiaju111 发表于 2007-6-17 18:00

楼上的方法似乎不对吧？ 第1次如果平衡呢，第2次取哪两个比较？

aipb2007 发表于 2007-6-17 18:09

都很不错，鉴定，可行！ 赞哈！！！

野比发表于 2007-6-17 18:19

发现问题了.. 我的方法最差情况(一直平衡)会出现第3步只能确定出假币(1/2).而无法得到假币轻重... 多谢jiaju111兄提醒..

aipb2007 发表于 2007-6-17 20:12

to jiaju111： 很厉害也！怎么想到的？？？我想了N久也是4次！ 你怎么捕捉这个思想的？？？分享一下哈！！！

jiaju111 发表于 2007-6-17 20:29

谢谢！ 其实我也是碰运气刚好想到而已 感觉这个就跟心理上的“换位思考”差不多 具体我也说不清楚，呵呵，不好意思啊

aipb2007 发表于 2007-6-17 20:32

<DIV class=quote>以下是引用jiaju111在2007-6-17 20:29:12的发言： 
谢谢！ 其实我也是碰运气刚好想到而已 感觉这个就跟心理上的“换位思考”差不多 具体我也说不清楚，呵呵，不好意思啊</DIV>
[em10] [em17]

页: 1 [2] 3 4 5 6 7 8 9 10 11