網域名稱俱樂部


返回   網域名稱俱樂部 > 電腦與網路技術 > 電腦網路相關技術 > 一般軟體與網路使用討論
論壇幫助 社區 日曆事件 今日新文章 搜尋

回覆
 
主題工具
  #1  
舊 2014-02-13, 08:29 PM
哈啦 的頭像
哈啦 哈啦 目前離線
論壇管理員
 
註冊日期: 2002-05-28
文章: 23,053
預設 一些和電腦語言有關的數學問題

我剛在看一個c語言的數字排序方法,用所謂的泡泡式排法。有看沒有懂

我是想先了解一下,假設有n個數字(n>=3)要兩兩比大小,來排序,有沒有公式知道是要比幾次?
例如有abc三個數字,先拿a比b,再來a比c,再拿b比c,這樣是三次。但如果是有abcd四個數字,a:b, a:c, a:d, b:c, b:d, c:d好像就要六次?到底有規律嗎?

thanks
__________________
咖啡走路
微博


您是網站站長嗎?歡迎到站長俱樂部 一起討論吧。
按我看版規
code.club
回覆時引用此篇文章
  #2  
舊 2014-02-13, 08:55 PM
yumi yumi 目前離線
進階會員
 
註冊日期: 2005-12-29
文章: 1,373
預設

比较次数=n*(n-1)/2
__________________
收购各位版友的四字母com、数字米com/net/cc、三杂米com、拼音米。价格随行市价。站内联系。
回覆時引用此篇文章
  #3  
舊 2014-02-13, 08:58 PM
lukawa lukawa 目前離線
進階會員
 
註冊日期: 2002-09-23
文章: 117
預設

bubble sort 算是用來瞭解排序跟練習排序程式最好的algorithm
他的最佳時間複雜度是O(n)
最差的時間複雜度是 O(n^{2})
重點是平均時間複雜度 O(n^{2}) !!

所以大一點的資料,千萬不要用bubble sort,那會排死

舉個例子

1 2 3 4 5 6 7

由小排到大,只要比較n=6次,得到最佳時間複雜度

但是如果要由大排到小
那就慘了

第一次比較6次會變成

2 3 4 5 6 7 1

第二次比較5次會變成

3 4 5 6 7 2 1

....一直下去

所以得到最差的時間複雜度 O(n^{2})
回覆時引用此篇文章
  #4  
舊 2014-02-13, 09:13 PM
weiye 的頭像
weiye weiye 目前離線
進階會員
 
註冊日期: 2006-05-16
文章: 305
預設

例如五個數字原本由左至右為 ④, ⑤, ②, ③, ①

想要將它由左至右~ 變成從小到大的順序~

由 ④ 開始,將其依序與它左邊的 ⑤, ②, ③, ① 比大小,

如果發現對方比較小就交換位置~

       ④, ⑤, ②, ③, ①
       └──┘
第一次比較: 沒有比較小,不換


       ④, ⑤, ②, ③, ①
       └────┘
第二次比較: 有比較小,交換,變成 ②, ⑤, ④, ③, ①

       ②, ⑤, ④, ③, ①
       └───────┘
第三次比較: 沒有比較小,不換

       ②, ⑤, ④, ③, ①
       └─────────┘
第四次比較: 有比較小,交換,變成 ①, ⑤, ④, ③, ②

經過四次比較,可以挑出最小的放在最左邊,

       ①, ⑤, ④, ③, ②
         ^^^^^^^^^^^^^^還沒有挑選的

同上述程序,可以 "再" 經由三次比較挑出 ⑤, ④, ③, ② 中最小的,

放在這四個數字的最左邊,變成 ①, ②, ⑤, ④, ③

                   ^^^^^^^^^^還沒有挑選的

餘同理。

因此,五個數字的泡泡排序法,須經過 4+3+2+1 = 4*(4+1)/2 次比較,完成排序。

因此, n 個數字的泡泡排序法,須經過 (n-1)+(n-2)+(n-3)+....+2+1 = (n-1)*[(n-1)+1]/2 次比較,完成排序。
__________________
Life, it is. https://sky.tw
回覆時引用此篇文章
  #5  
舊 2014-02-13, 09:24 PM
哈啦 的頭像
哈啦 哈啦 目前離線
論壇管理員
 
註冊日期: 2002-05-28
文章: 23,053
預設

十分感謝各位。

果然是有公式的,數學不學好還真是不行啊,我抽象觀念差,光靠想的真的想不出來,後來自己用指頭算



但以下這個程式寫法,我就是搞不懂紅藍字的部份,why它會如此寫 ?

代碼:
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	
	int item[100];
	int a,b,t;
	int count;
	
	printf("how many numbers? \n");
	scanf("%d",&count);
		for(a=0;a<count;a++) 	scanf("%d", &item[a]);
	
	for(a=1;a<count;a++)
	  for(b=count-1;b>=a;b--)
	  {
	  	if (item[b-1]>item[b]) {
	  		t=item[b-1];
	  		item[b-1]=item[b];
	  		item[b]=t;
	  	}
	  }
	  for(t=0;t<count;t++) printf("%d\n",item[t]);
	  return 0;
	}
假設我要將十個數字排序,紅字的地方顯然是從1開始而小於count(10)就是只從1到9,算9次而已。

這樣說吧,剛開始a=1,b=count-1就是從9開始往下減,最後減到>=a就是減到1,可是陣列的第一個元素排序不是0嗎?最前面那個就不比了嗎?
__________________
咖啡走路
微博


您是網站站長嗎?歡迎到站長俱樂部 一起討論吧。
按我看版規
code.club
回覆時引用此篇文章
  #6  
舊 2014-02-14, 10:04 AM
lukawa lukawa 目前離線
進階會員
 
註冊日期: 2002-09-23
文章: 117
預設

請看這行 if (item[b-1]>item[b]) {
當b = 1 時,這行就會是 item[0]>item[1]
這樣第0個也有比到
回覆時引用此篇文章
  #7  
舊 2014-02-14, 12:22 PM
哈啦 的頭像
哈啦 哈啦 目前離線
論壇管理員
 
註冊日期: 2002-05-28
文章: 23,053
預設

引用:
作者: lukawa 查看文章
請看這行 if (item[b-1]>item[b]) {
當b = 1 時,這行就會是 item[0]>item[1]
這樣第0個也有比到
I see, thank you!
__________________
咖啡走路
微博


您是網站站長嗎?歡迎到站長俱樂部 一起討論吧。
按我看版規
code.club
回覆時引用此篇文章
  #8  
舊 2014-02-14, 03:32 PM
some some 目前離線
進階會員
 
註冊日期: 2003-09-23
住址: 屏東
文章: 3,612
預設

哈大~

一點建議... 如果不是瘋狂的程式設計者.. 這種東西找現成函式來套就好, 才省時間
把大部份的思考用在想呈現的邏輯上

比方說~ 開車老強的舒馬克, 用不著知道輪胎要用什麼摩擦系數的最好, 換輪胎的技師也不用知道輪胎怎麼做的~~

我寫過很多程式 類似這種的東西我也練習過, 但想通了寫成了過沒幾個月再看一次, "又得重想一下".. 所以我現在都直接跳過節省我寶貴的時間
__________________
nice to meet you                   flickr
回覆時引用此篇文章
  #9  
舊 2014-02-14, 03:56 PM
哈啦 的頭像
哈啦 哈啦 目前離線
論壇管理員
 
註冊日期: 2002-05-28
文章: 23,053
預設

引用:
作者: some 查看文章
哈大~

一點建議... 如果不是瘋狂的程式設計者.. 這種東西找現成函式來套就好, 才省時間
把大部份的思考用在想呈現的邏輯上

比方說~ 開車老強的舒馬克, 用不著知道輪胎要用什麼摩擦系數的最好, 換輪胎的技師也不用知道輪胎怎麼做的~~

我寫過很多程式 類似這種的東西我也練習過, 但想通了寫成了過沒幾個月再看一次, "又得重想一下".. 所以我現在都直接跳過節省我寶貴的時間
thanks

不過我學這個的初始目的只是要讓腦筋活動一下,所以不趕時間也沒啥目的,因此可以慢慢地去搞通一些邏輯上的東西,這剛好有助於延緩我的老年痴呆進程

其實我也建議各位到中年以上的版友們,再找些新的東西來讓腦筋活動一下。活動的標準就是你看了會覺得傷腦筋,一個頭兩個大的新東西才比較有效。雖說保持閱讀是讓大腦不退化的好方法,但一般人的閱讀傾向是專挑自己能輕鬆閱讀的內容,據說這樣的效果不是很好。腦力和肌力一樣,練完如果沒有酸痛感,效果就比較差一點。
__________________
咖啡走路
微博


您是網站站長嗎?歡迎到站長俱樂部 一起討論吧。
按我看版規
code.club
回覆時引用此篇文章
回覆


發文規則
不可以發表新主題
不可以發表回覆
不可以上傳附件
不可以編輯自己的文章

啟用 BB 代碼
論壇啟用 表情符號
論壇啟用 [IMG] 代碼
論壇禁用 HTML 代碼



所有時間均為 +8。現在的時間是 07:34 AM


本站主機由網易虛擬主機代管
Powered by vBulletin® 版本 3.8.4
版權所有 ©2000 - 2024,Jelsoft Enterprises Ltd.