• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 6, 文章 - 0, 評(píng)論 - 24, 引用 - 0
            數(shù)據(jù)加載中……

            從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))

            從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維

            題目

             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


            題目分析
               題意是對(duì)于給定的n(n為奇數(shù))根木棒,其中有n - 1根是可以按長度配對(duì)的,找出按長度配對(duì)后剩余的一根木棒。
               下面給出這題的幾種解法:
               (1)對(duì)于每根木棒,都搜索與其匹配的另一根木棒,時(shí)間復(fù)雜度為O(n2);
               (2)先將木棒按其長度排序,然后依次掃描各相鄰木棒是否匹配,時(shí)間復(fù)雜度為O(nlogn);
               (3)對(duì)于任意的x,都滿足如下公式:x Xor 0 = x, x Xor x = 0。而且異或操作是滿足交換律和結(jié)合律的,因此所有配對(duì)的木棒異或后結(jié)果為0,因此將所有木棒的長度異或后得到的結(jié)果即為不成對(duì)的那根木棒的長度,時(shí)間復(fù)雜度為O(n)。

            思考題

               (1)有長度為1到n共n根木棒,現(xiàn)從中拿走某一根,再放入一根任意長度的木棒。順次輸入這n根木棒的長度,求拿走與放入木棒的長度分別是多少?
               (2)有n根木棒,其中有多于一半的木棒其長度相等,順次輸入所有木棒的長度,求出這些長度相等的木棒的長度是多少?

            參考資料

            郭嵩山、張子臻、王磊、湯振東著  國際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解(五)  電子工業(yè)出版社

            posted on 2009-03-29 23:38 yuyang7 閱讀(2401) 評(píng)論(9)  編輯 收藏 引用 所屬分類: 程序設(shè)計(jì)競(jìng)賽

            評(píng)論

            # re: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))  回復(fù)  更多評(píng)論   

            支持,希望LZ以后多出點(diǎn)算法類型的文章。。。
            2009-03-30 12:32 | funcoding

            # re: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))  回復(fù)  更多評(píng)論   

            @funcoding
            謝謝支持。
            我可能會(huì)比較多的寫一些介紹數(shù)據(jù)結(jié)構(gòu)或算法的文章,關(guān)于解題的不會(huì)太多。

            2009-03-30 12:48 | yuyang7

            # re: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))  回復(fù)  更多評(píng)論   

            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: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))  回復(fù)  更多評(píng)論   

            這種是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: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))[未登錄]  回復(fù)  更多評(píng)論   

            @黃宇
            不好意思,樓上可能理解錯(cuò)了題意.題目只說有n<= 100根木棒,并沒有說每根木棒的長度也在100以內(nèi).
            2009-03-31 11:20 | yuyang7

            # re: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))  回復(fù)  更多評(píng)論   

            異或...

            題目還可以再變一下:
            有n種長度的棍子
            其中n-1種長度的有3根,剩下1種長度的只有2根.求那個(gè)長度...:)

            # re: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))  回復(fù)  更多評(píng)論   

            如果題目變?yōu)闃巧险f的那樣的話,我只能想到排序,不知樓上有何高見。
            求解答!!!!
            2009-03-31 18:00 | yuyang7

            # re: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))[未登錄]  回復(fù)  更多評(píng)論   

            把n個(gè)數(shù)直接異或,結(jié)果就是要求的那個(gè)剩余長度了。
            2009-04-01 11:37 | haha

            # re: 從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維(續(xù))  回復(fù)  更多評(píng)論   

            呃..偶然路過...關(guān)于那個(gè)變種,不知LZ現(xiàn)在有答案了沒有.

            異或的本質(zhì)是每一bit分別模2加.. 所以針對(duì)那個(gè)變種, 換成模3加即可
            97久久天天综合色天天综合色hd| 精品人妻伦九区久久AAA片69 | 久久久免费观成人影院| 99久久精品无码一区二区毛片 | 久久本道伊人久久| 久久国产精品久久国产精品| 国内精品久久久久影院免费| 久久99国产精品久久99| 99久久精品这里只有精品| 品成人欧美大片久久国产欧美...| 伊人久久大香线蕉影院95| 久久久久久国产精品美女| 中文国产成人精品久久亚洲精品AⅤ无码精品| 久久久久久亚洲精品不卡| 怡红院日本一道日本久久 | 久久久精品人妻无码专区不卡| 精品人妻伦九区久久AAA片69| 免费精品久久久久久中文字幕| 亚洲日本久久久午夜精品| 久久婷婷激情综合色综合俺也去| 69国产成人综合久久精品| 99热精品久久只有精品| 国产69精品久久久久APP下载 | 亚洲国产欧美国产综合久久| 久久综合久久综合久久综合| 无码8090精品久久一区| 久久av无码专区亚洲av桃花岛| 国产精品免费久久| 亚洲精品无码久久久久去q| 国内精品久久久久久久亚洲| 久久精品久久久久观看99水蜜桃| 99精品国产在热久久无毒不卡| 久久久久亚洲av毛片大| 久久中文骚妇内射| 亚洲七七久久精品中文国产| 久久91精品国产91久久麻豆| AV无码久久久久不卡蜜桃| 久久国产香蕉视频| 久久精品人人做人人爽电影| 久久久噜噜噜久久中文字幕色伊伊| 久久线看观看精品香蕉国产|