幫幫忙一下!!提式一下吧

MyChat 數位男女

»
程式設計

手機版

地圖

簡體

您是第 3251 個閱讀者

<< 1 2 下頁 >>

(共 2 頁)

可列印版加為IE收藏收藏主題上一主題 | 下一主題

孫子兵法

級別: 路人甲

▼

[C/C++][求助] 幫幫忙一下!!提式一下吧

練習的時候碰到一個題目:
palindrome(包含一個單字或是一個去掉空白、逗點的字串，不論大小寫字母，前後完全對稱者)

試寫一遞迴函數，如果輸入之字 ..

訪客只能看到部份內容，免費加入會員或由臉書 Google 可以看到全部內容


x0 [樓主] From：東森 Cable \| Posted：2007-06-10 23:24 \|

ety

級別: 初露鋒芒

x719

▲ ▼

把字串長度除以二, 那麼字串就一分為二, 變成兩個子字串了!
把後面那一段子字串裡的字元以相反的順序排列, 然後再拿來與前面那一段子字串比對!

我是猜的, 你試看看!


x0 [1 樓] From：臺灣和信超媒體寬帶網 \| Posted：2007-06-11 04:08 \|

gamewalk

級別: 初露鋒芒

x18

▲ ▼

作法應該就是先取得長度,再用兩個數當索引值一個從字串頭,另一個從字串尾,分別遞增及遞減一一比對,至於如何避開,點和空白以及不論大小寫自己想吧...


x0 [2 樓] From：臺灣永大數位動力公司 \| Posted：2007-06-11 05:15 \|

a86980

級別: 小有名氣

x64

x1308

▲ ▼

第1迴圈
從第一字元讀到最後一個字元
記下總數(去除符號)

第2迴圈(=總數)
再從最後一個字元遞減到開始字元

如果第1迴圈=第2迴圈則傳1
反之傳回0

應該是這樣吧


x0 [3 樓] From：臺灣 \| Posted：2007-06-12 22:41 \|

ety

級別: 初露鋒芒

x719

▲ ▼

看了一下, 我認為你還是用我的方法會比較好唷!
把長度除以二, 只將後半段反轉順序再比對, 很快!
若用他們的方法, 整個字串反轉再比對不但記憶體用得比較兇, 連時間複雜度 big O 都增加許多!
而且拿 Madam I'm Adam 來當例子好了, 用我的方法, 是比對 Madam 與 madA m! 他們的方法則是比對整個字串, Madam I'm Adam 與 madA m'I madaM, 想想看, 一定更麻煩的...


x0 [4 樓] From：臺灣和信超媒體寬帶網 \| Posted：2007-06-13 01:53 \|

gamewalk

級別: 初露鋒芒

x18

▲ ▼

下面是引用ety於2007-06-13 01:53發表的 :
看了一下, 我認為你還是用我的方法會比較好唷!
把長度除以二, 只將後半段反轉順序再比對, 很快!
若用他們的方法, 整個字串反轉再比對不但記憶體用得比較兇, 連時間複雜度 big O 都增加許多!
而且拿 Madam I'm Adam 來當例子好了, 用我的方法, 是比對 Madam 與 madA m! 他們的方法則是比對整個字串, Madam I'm Adam 與 madA m'I madaM, 想想看, 一定更麻煩的...

不過ety大大...我有個疑問 , 我剛剛算了一下 , 這個字串有14個字元 , 長度除以2 切割後...
一個為 : Madam I
另一個為 : 'm Adam 反轉後 madA m'
兩者都去掉空白以及其他符號同時再把它們都轉成大寫..
MADAMI
MADAM
這樣子比對應該會被認為不對稱吧....因為前者多了一個 I
( 還是說我誤解你意思了 , 如果有弄錯的話...抱歉^^" )

還有其實我說的作法是只要用一個while迴圈就可以達成的 , 一取得字串長度就可以開始比了...而且並非比完整個字串 ...

[ 此文章被gamewalk在2007-06-13 04:01重新編輯 ]


x0 [5 樓] From：臺灣永大數位動力公司 \| Posted：2007-06-13 03:50 \|

ety

級別: 初露鋒芒

x719

▲ ▼

要先除去符號, 空白以及轉變大小寫唷!

"Madam I'm Adam" 會變為 "MadamImAdam", 就如我之前說的, 字串一分為二且反轉後半段, 只要比對 Madam 與 madAm! (MadamImAdam長度為十一, 除二為五, 不考慮餘數, 所以 I 不用管)

我把我的方法實作出來了, 的確可行!

我的方法花了兩個變數空間, 各儲存了長度為5的字串, 你的方法是存完整字串的長度耶...
我的方法比對時是比對兩個長度為5的字串, 你的是比對完整字串耶...

不管你取得長度後是一個字元對一個字元比對, 還是整個字串比對, 我的用量都比你少!
就算用迴圈, 我跑的圈數也比你少!

你有沒有聽過遞迴這種程式寫法呢?
這種方法的程式碼通常比一般方法的程式碼來得少, 也簡單. 但時間複雜度與記憶體的用量也比一般用法驚人...

所以就算精簡程式碼, 也不見得有效率唷


x0 [6 樓] From：臺灣和信超媒體寬帶網 \| Posted：2007-06-13 20:00 \|

gamewalk

級別: 初露鋒芒

x18

▲ ▼

的確你的方法是在除去符號空白及轉完大小寫後就能實現...但是如果同樣的除去符號空白及轉完大小寫條件下用while迴圈也只要跑5次吧...

還有一件事希望ety大大別介意 , 其實當自己的程式被質疑說瑕疵時難免會想要辯解 , 我有可能一時被你前面講的話影響到 , 才會一時衝動有點預設立場的質疑你的程式


x0 [7 樓] From：臺灣永大數位動力公司 \| Posted：2007-06-13 22:34 \|

ety

級別: 初露鋒芒

x719

▲ ▼

為什麼要哭喪著臉呢... = ="

程式當然要質疑一下, 最好還要親自開發看看! 你看不明白我的說法, 那表示其它人或許也會看不懂, 所以我就再說明清楚一點, 這樣不就大家都了解了嗎? ^^

求出長度後用 while (遞減的方式來比對) 來說, 你要如何在長度一半(這裡指5)內比對呢? 應該要跑到底才對了... 若用 for 就有可能了!


x0 [8 樓] From：臺灣和信超媒體寬帶網 \| Posted：2007-06-13 23:17 \|

gamewalk

級別: 初露鋒芒

x18

▲

假設在轉完的情況下
複製程式

int Checkpalindrome()
{
    int i,j;
    char Str[] = "MADAMIMADAM"; //假設已將"Madam I'm Adam"轉換完畢好了 
    i=0;   //從字串頭
    j=strlen(Str) - 1; //從字串尾
    while( i < j )
    { 
           if( Str[i] == Str[j] )
           {
               i++;
               j--; 
           }
           else
           {
                return 0; 
           } 
    }
    return 1; 
}

如果沒有問題第五次跑完 I不用比就結束了....
不過你講的時間複雜度...我真的不是很熟所以我也沒有辦法反駁你

剛才才注意到樓主似乎有要求要用遞回寫....可能要在改一下才會符合樓主的題目要求...
不過我只是先舉個例...

[ 此文章被gamewalk在2007-06-14 00:11重新編輯 ]


x0 [9 樓] From：臺灣永大數位動力公司 \| Posted：2007-06-13 23:53 \|

<< 1 2 下頁 >>

(共 2 頁)

Powered by PHPWind v1.3.6 Copyright © 2003-04 PHPWind	Processed in 0.058328 second(s),query:16 Gzip disabled 本站由瀛睿律師事務所擔任常年法律顧問 \| 免責聲明 \| 本網站已依台灣網站內容分級規定處理 \| 連絡我們 \| 訪客留言