随笔 - 6, 文章 - 0, 评论 - 24, 引用 - 0
数据加载中……

从一道简单题谈程序设计的思维(续)

从一道简单题谈程序设计的思维

题目

 Stick
Problem 

Anthony has collected a large amount of sticks for manufacturing chopsticks. In order to simplify his job, he wants to fetch two equal-length sticks for machining at a time. After checking it over, Anthony finds that it is always possible that only one stick is left at last, because of the odd number of sticks and some other unknown reasons. For example, Anthony may have three sticks with length 1, 2, and 1 respectively. He fetches the first and the third for machinning, and leaves the second one at last. Your task is to report the length of the last stick.

Input

The input file will consist of several cases.
Each case will be presented by an integer n (1 <= n <= 100, and n is odd) at first. Following that, n positive integers will be given, one in a line. These numbers indicate the length of the sticks collected by Anthony.
The input is ended by n = 0.

Output

For each case, output an integer in a line, which is the length of the last stick.

Sample Input
3
1
2
1
0
Sample Output
2


题目分析
   题意是对于给定的n(n为奇数)根木棒,其中有n - 1根是可以按长度配对的,找出按长度配对后剩余的一根木棒。
   下面给出这题的几种解法:
   (1)对于每根木棒,都搜索与其匹配的另一根木棒,时间复杂度为O(n2);
   (2)先将木棒按其长度排序,然后依次扫描各相邻木棒是否匹配,时间复杂度为O(nlogn);
   (3)对于任意的x,都满足如下公式:x Xor 0 = x, x Xor x = 0。而且异或操作是满足交换律和结合律的,因此所有配对的木棒异或后结果为0,因此将所有木棒的长度异或后得到的结果即为不成对的那根木棒的长度,时间复杂度为O(n)。

思考题

   (1)有长度为1到n共n根木棒,现从中拿走某一根,再放入一根任意长度的木棒。顺次输入这n根木棒的长度,求拿走与放入木棒的长度分别是多少?
   (2)有n根木棒,其中有多于一半的木棒其长度相等,顺次输入所有木棒的长度,求出这些长度相等的木棒的长度是多少?

参考资料

郭嵩山、张子臻、王磊、汤振东著  国际大学生程序设计竞赛例题解(五)  电子工业出版社

posted on 2009-03-29 23:38 yuyang7 阅读(2372) 评论(9)  编辑 收藏 引用 所属分类: 程序设计竞赛

评论

# re: 从一道简单题谈程序设计的思维(续)  回复  更多评论   

支持,希望LZ以后多出点算法类型的文章。。。
2009-03-30 12:32 | funcoding

# re: 从一道简单题谈程序设计的思维(续)  回复  更多评论   

@funcoding
谢谢支持。
我可能会比较多的写一些介绍数据结构或算法的文章,关于解题的不会太多。

2009-03-30 12:48 | yuyang7

# re: 从一道简单题谈程序设计的思维(续)  回复  更多评论   

int main()
{
int n;
cin >> n;
set<int> data;
for (int i = 0; i < n; i++)
{
int tmp;
cin >> tmp;
if (data.find(tmp) != data.end())
{
data.erase(tmp);
}
else
data.insert(tmp);
}
copy(data.begin(), data.end(), ostream_iterator<int>(cout," "));
return 1;
}
2009-03-30 23:14 | 黄宇

# re: 从一道简单题谈程序设计的思维(续)  回复  更多评论   

这种是o(n)的
=====================================
static bool data[101] = {0};

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int tmp;
cin >> tmp;
if (data[tmp])
{
data[tmp] = 0;
}
else
data[tmp] = 1;
}
for (int i = 1; i < 100; i++)
{
if (data[i] == 1)
{
cout << i << endl;
}
}
}
2009-03-30 23:27 | 黄宇

# re: 从一道简单题谈程序设计的思维(续)[未登录]  回复  更多评论   

@黄宇
不好意思,楼上可能理解错了题意.题目只说有n<= 100根木棒,并没有说每根木棒的长度也在100以内.
2009-03-31 11:20 | yuyang7

# re: 从一道简单题谈程序设计的思维(续)  回复  更多评论   

异或...

题目还可以再变一下:
有n种长度的棍子
其中n-1种长度的有3根,剩下1种长度的只有2根.求那个长度...:)

# re: 从一道简单题谈程序设计的思维(续)  回复  更多评论   

如果题目变为楼上说的那样的话,我只能想到排序,不知楼上有何高见。
求解答!!!!
2009-03-31 18:00 | yuyang7

# re: 从一道简单题谈程序设计的思维(续)[未登录]  回复  更多评论   

把n个数直接异或,结果就是要求的那个剩余长度了。
2009-04-01 11:37 | haha

# re: 从一道简单题谈程序设计的思维(续)  回复  更多评论   

呃..偶然路过...关于那个变种,不知LZ现在有答案了没有.

异或的本质是每一bit分别模2加.. 所以针对那个变种, 换成模3加即可

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理