2014年12月10日 星期三

演算法訓練 1 ─ 平均演算法

http://4rdp.blogspot.com/2014/12/1.html

二十一世紀是機器人盛行的世代,有鑑於程式設計重要性越來越重要,看數學訓練感系列文章頗受好評,因此想安插一些有助學習程式設計的演算法問題,讓大家思考討論,雖然我不是這方面專家,不過順便收錄各類演算法,也是不錯的收穫。

請設計一演算法,它能於每秒鐘收入一筆數值資料,試求出自記錄啟動後,它的平均值、最大值與最小值。

這個演算法是一般數位電表最基本的計算功能,平時量測看數字跳來跳去,不易閱讀取值,啟動這功能後,可以獲得穩定數值紀錄,並且也知道數值變動範圍,經常在測量資料的人可以寫一個副程式引用。它的設計關鍵在以最少的記憶體紀錄,因為測量資料源源不絕產生,要隨時平均資料並記錄最大、最小值。

這裡所出的題目,不限制程式語言,甚至以純文字表述也歡迎,就算有人已經以某種語言發表答案,也歡迎你用更精簡方式或是其它程式語言再重製,一個好的程式,應同時注重程式碼大小、占用記憶體資源與執行效率。在此貼出的程式碼,著作權除非另有聲明,否則屬貼文者的,其內容純研究討論供大眾參考,也不負任何使用損壞賠償責任。

12 則留言:

  1. 很有趣的題目,我列出pdf檔案,請大家指正。
    http://www.slideshare.net/renchiou/avgminmax223

    回覆刪除
    回覆
    1. 邱老師好久不見,這個單元你搶得頭香,厲害厲害,歡迎你分享程式。

      刪除
    2. 謝謝Bridan先生。我已經將ev3檔案上傳到
      http://goo.gl/ILExHL
      請大家下載執行,歡迎討論。

      刪除
    3. 謝謝邱老師參與,星期三將會有新題目發佈,它也適合 EV3 作答,歡迎老師屆時搶答。^_^

      刪除
  2. 我是以matlab為操作工具,程式碼如下:
    clear all
    clc

    data=[100 90 80 60 80 90 75 70 80 100];
    n=size(data,2);
    sum=0;
    average_value=0;

    for i=1 :10
     if i==1
      max_value=data(i); 
      min_value=data(i);
     end
     
     sum=sum + data(i);

     if data(i)>max_value
       max_value= data(i);
     end

     if data(i)<min_value
      min_value=data(i);
     end
     fprintf('第%d筆資料=%d,讀取完畢\n',i,data(i))
     pause(1);
    end
    fprintf('-------------\n')
    average_value=sum/n;
    fprintf('平均值=%3.2f\n',average_value)
    fprintf('最大值=%d\n',max_value)
    fprintf('最大值=%d\n',min_value)

    回覆刪除
  3. 影片結果:https://www.youtube.com/watch?v=JZhv-OIad-8&feature=youtu.be

    回覆刪除
    回覆
    1. 感謝薛老師共襄盛舉,這麼晚沒睡,辛苦了。^_^

      刪除
  4. 我會用四個記憶體空間資料數、平均值、最大值與最小值
    我的平均值更改為最後的N筆資料的平均
    最後的N筆資料的平均=(最後的N-1筆資料的平均*(N-1)+目前值)/N
    資料數就的大小越大會越精準,但使用的空間就變大了

    回覆刪除
    回覆
    1. Yuying 您好,記憶體受限時,實作上是採用這種方法沒錯,謝謝妳的補充。

      加分題,你會選用何種資料型態儲存這些數值?如果空間資料數值爆滿時,該如何處理?

      刪除
  5. 平均數演算法, 修改 Yuying Zheng 的演算法:
    average_(n)=average_(n-1) + [(X_n - average_(n-1)) ] / n
    避免當 n 很大時, 平均數 * (n-1) 溢位, 及增加平均值的精度(牽扯到浮點數的有效位數)。但是 n 越來越大時,卻同時影響到 (X_n - average_(n-1)) / n 的精準度。

    n 會使用 unsigned long (64bit unsigned long integer 是: 0 ~ 18,446,744,073,709,551,615)
    其他應該使用 float 就足夠。當然,如果要求更精確,會用到 double.

    回覆刪除
  6. 我要修正。 n 其實可以不需要用到 unsigned long. 因為... 18,446,744,073,709,551,615 秒 = 5.8 E 14 年.... 沒有人或者機器人可以 "活 這麼久,用這麼久。

    回覆刪除
  7. 嗯,避免溢位必須採取你的方法,使用 float (32 bits) 儲值,精度可以達五位半數值,這樣一般場合是夠用,n 用 32 bits unsigned long 就夠,每秒一筆相當於六年四個月夠久了,除非這東西要上太空找 ET。

    看似簡單的題目暗藏玄機很多。這題先討論到此,進階問題將後續幾週陸續提出。

    回覆刪除