• <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, 評論 - 24, 引用 - 0
            數(shù)據(jù)加載中……

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

            從一道簡單題談程序設(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


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

            思考題

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

            參考資料

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

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

            評論

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

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

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

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

            2009-03-30 12:48 | yuyang7

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

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

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

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

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

            異或...

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

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

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

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

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

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

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

            異或的本質(zhì)是每一bit分別模2加.. 所以針對那個變種, 換成模3加即可
            亚洲国产精品综合久久网络| 久久午夜无码鲁丝片午夜精品| 亚洲精品无码久久久久AV麻豆| 久久国产精品二国产精品| 久久国产成人精品国产成人亚洲| 99久久精品免费看国产免费| 久久一本综合| 三上悠亚久久精品| 欧美一级久久久久久久大片| 久久久久久免费一区二区三区| 国产欧美久久久精品影院| 久久综合狠狠色综合伊人| 色偷偷91久久综合噜噜噜噜| 久久精品中文无码资源站| 久久久久亚洲AV无码专区首JN | 久久天天躁狠狠躁夜夜2020| 久久精品国产清自在天天线| 久久99热这里只有精品国产| 九九久久自然熟的香蕉图片| 久久中文字幕人妻丝袜| 成人a毛片久久免费播放| 久久精品国产只有精品2020| 中文字幕人妻色偷偷久久| 日韩电影久久久被窝网| aaa级精品久久久国产片| 韩国免费A级毛片久久| 一级女性全黄久久生活片免费| 精品无码久久久久久久动漫| 久久精品天天中文字幕人妻| 精品久久久久久无码不卡| 欧美久久久久久午夜精品| 久久婷婷国产麻豆91天堂| 国产亚洲婷婷香蕉久久精品| 久久久一本精品99久久精品66| 久久99热这里只有精品国产| 亚洲欧美一区二区三区久久| 久久综合久久性久99毛片| 久久久精品久久久久久| 久久九九兔免费精品6| 99久久香蕉国产线看观香| 欧美日韩精品久久久久|