頁:
[1]
請問這Code演算法還有改進空間嗎
輸出格式:在每行印出印出每對客人的體重及其總和(總和 = 較重的體重 + 較輕的體重)
由最重的體重總合開始 依體重總和順序由重向輕印出。
若體重總和相同時 按照客人的體重順序 重者先印
Example:
input:
10 (這是人數)
92
13
74
84
45
36
57
67
25
7
output:
103 = 67 + 36
102 = 57 + 45
99 = 92 + 7
99 = 74 + 25
97 = 84 + 13
這是我的Code 這是我想了一陣子 寫出來的 不過 想問問有捨 更有效率的演算法 討論討論
http://www.mediafire.com/?yhzkiszsc9mvspg...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div> 我有問題~(舉手)cin >> n;
int a;這兩行~可以通過嗎?
我記得~~好像不行吧!? 排序可以用內建快排… 實作輕鬆, 效率有保證, 沒有不用的原因～
代碼大致上如下
#include<algorithm>
...
sort ( a, a+n );
詳情可以參閱cppreference - sort的使用方法
其次是輸出答案的時候可以更快的，因為你可以設定一個數組p，存放s代表哪一組a。這樣做便可以省卻配對答案的時間。
至於算法的構思還是蠻直觀的…而題目似乎一定要先將a排序，所以我相信不能擺脫排序的下界O(n log n)。...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 本帖最後由 tony01111299 於 2011-6-29 04:30 AM 編輯
單就排序的部分來看，可以改成如下的 code：for(int flag=0,i=n-1;i>=0;flag=0,i--){
for(j=0;j<i;j++){ // 第 x 次排序時，後面數來 n-x+1 項已排好
// 故不需做多餘檢查
if(a<a){
int temp=a;
a=a;
a=temp;
flag=1;
}
}
if(!flag) // !flag 即內迴圈無做任何排序動作，表示已經排好無需繼續再做
break;
}另外這邊其實也可以用 quick sort 下去做，當資料量極大且未排序的時候會有明顯的差別。大致講一下它的演算法：
假設目前有 10 筆資料，依序為 355 921 36 456 194 880 19 561 872 988，則
355 921 36 456 194 880 19 561 872 988 // 355 不大於 988，不交換且指標往前移
355 921 36 456 194 880 19 561 872 988
355 921 36 456 194 880 19 561 872 988
355 921 36 456 194 880 19 561 872 988 // 355 大於 19，交換且指標移到另一端標記並往後移
19 921 36 456 194 880 355 561 872 988 // 355 小於 19，交換且指標移到另一端標記並往前移
19 355 36 456 194 880 921 561 872 988
19 355 36 456 194 880 921 561 872 988
19 194 36 355 456 880 921 561 872 988
19 194 36 355 456 880 921 561 872 988 // 指標指到自己，對前、後半部各自再做 quick sort
19 194 36 355 456 880 921 561 872 988
19 36 194 355 456 880 921 561 872 988
19 36 194 355 456 880 921 561 872 988 // 只有自己一個，直接 return
19 36 194 355 456 880 921 561 872 988
19 36 194 355 456 872 561 880 921 988
19 36 194 355 456 561 872 880 921 988
19 36 194 355 456 561 872 880 921 988
19 36 194 355 456 561 872 880 921 988
19 36 194 355 456 561 872 880 921 988
排序完成。
以一般的排列方法來看，100 筆資料若以簡單的數學呈獻大約要做 100+99+98+97+...+3+2+1=100×(100+1)÷2=5050 約 5000 次的比較排序；quick sort 大致為 100+(前部分 sort)+(後部分 sort)，假設資料亂得很平均每次的 flag 都大致落在中間，則此式可以大略表示成 100+(50+(25+(12+(6+(3+(1+1)+3)+6)+12)+25)+50)+(50+(25+(12+(6+(3+(1+1)+3)+6)+12)+25)+50) = 488 約 500 次的比較排序，可以看出 quick sort 在速度上有非常明顯的不同；但若碰上已排序的資料，會變成 1000+(999+(998+(997+(...)+0)+0)+0) 算出來做的次數會和一般排序差不多，遞迴呼叫函數又比 loop 慢上許多導致其速度反而會比一般排序法慢。
不過要做 quick sort 要用到蠻多東西去記錄當前狀況，像是目前的 flag 指到哪、switch 是在 tail 還是 head、tail/head 的位置指到哪（因為整個數列會逐漸往中間縮小）。不久前似乎有看到要用 loop 做出 quick sort 的帖子，理論上是可以的，但是你要想辦法記錄每一個分出來的 quick sort 對應到的 flag 是哪一個，當你在排 10000 筆資料可能反而變成在搞 20000 筆資料甚至更多更多的記錄器，是一個說得簡單做起來要人命的工作。...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 回復 4# tony01111299
請問大大你上面所說的方法 是使用到指標嗎??? 雙重指標??? 還是鏈結串列 ???
大大上面說的排序法 名稱是叫做快速排序法??? 沒有比較專業的名稱???
這麼說 通常很少會用我這麼排序法囉 (在資料大的時候)<br><br><br><br><br><div></div> 本帖最後由 tony01111299 於 2011-6-29 03:10 PM 編輯
回復 5# z24374203
沒有比較專業的名稱，英文 quick sort 直譯就是快速排序法，要說比較專業的名稱或許得問問英文系看看{:1_newsweat:}。
你的排序法是泡沫排序法，跟插入、選擇另外兩種排序法適合處理資料數少的排序；快速排序法則因整體架構比較複雜，在處理資料數少的排序反而會比泡沫、插入、選擇的效率差一些，故較適合處理資料數龐大的東西。
以 int* 舉例的話 quick sort 程式碼大致就像這樣子：void Qsort(int*a,int n)
{
if(n<=1)
return;
int head=0,tail=n-1,flag=0,side=0,tmp; // side==0 表 head, 1 表 tail
while(head!=flag || tail!=flag){
if(side==0){ // flag 在 head 端
if(a>a){ // 交換並更改相關訊息
tmp=a,a=a,a=tmp;
flag=tail;
side=1;
head++;
}
else
tail--;
}
else{ // flag 在 tail 端
if(a<a){ // 交換並更改相關訊息
tmp=a,a=a,a=tmp;
flag=head;
side=0;
tail--;
}
else
head++;
}
}
Qsort(a,flag);
Qsort(a+flag+1,n-flag-1);
} ...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 回復 2# baepi
好像要用到動態配置吧？int *a;
int n;
cin>>n;
a = new int;因為c＋＋很少再玩，所以沒寫錯的話應該是這樣？ 回復 7# trtc008056
我自己是知道要用動態 不過 為捨這樣打可以 也不是很清楚 回復 8# z24374203
你是用Dev?VC?還是？
剛剛用XCode測試了一下
還真的可以耶！！
可能是VC不讓我過吧＝"＝ 回復 9# trtc008056
那部份叫 可變長度陣列(VLA)
wiki 上之說明 於此
C/C++ 支援 VLA 是在 C99 以後，
Dev-C 沒特別試過，之前看別人試是可以的，
VC 只支援到 C90，M$ 也揚言不打算從 C99，
所以 VC 底下不支援 VLA<br><br><br><br><br><div></div> 回復 10# goodbye_mylove
了解，所以只是C90與C99的差別了
dev我沒裝，可能要叫別人是是看了
話說dev最後一次更新是再n年前，不知道有沒有支援 回復 11# trtc008056
DEV C++ 是OK的 我有跑過 樓主是用泡沫排序做的吧(下意識看錯以為用選排(汗))
一般而言大部分都是用快排去做排序的動作
頁:
[1]