|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
โปรแกรม คำนวณหาผลรวมของตัวหารแท้
ตรงเฉลยข้อ 5 (http://www.mathcenter.net/ntheory/ntheory01/ntheory01p04.html) ของแบบฝึกหัดในเรื่องทฤษฎีจำนวนบทที่ 1 (http://www.mathcenter.net/ntheory/ntheory01/ntheory01p01.html) หนะครับ
ตรงส่วนที่คำนวณหาผลรวมของตัวหารแท้หนะครับ long y = 0; for (long i = 1; i<=(x/2); i++) if ((x%i) == 0) y += i; ผมสามารถคิดวิธีที่คำนวณได้เร็วกว่านี้ครับ ผมลองใช้ perl เขียนได้อย่างนี้ครับ my $y = 1; my $temp = sqrt($x); for (my $i = 2; $i < $temp; $i++) { use integer; if (($x%$i) == 0) { $y += $i + $x/$i; }; }; if (int($temp) == $temp) { $y += $temp; }; ถ้าใช้ภาษา C ก็คงออกมาเป็นอย่างนี้ครับ long y = 1; float temp = sqrt(x); for (long i = 2; i < temp; i++) { if ((x%i) == 0) y += i + x/i; }; if (int(temp) == temp) y += temp; ตัวที่เป็นภาษา C ยังไม่ได้ทดสอบครับว่ามี bug รึเปล่า แต่ตัวที่เป็น perl นั่นลองรันทดสอบแล้วครับ ถ้าเป็นแบบที่เฉลยไว้จะใช้ time complexity เป็น O(x^2) ครับ แต่วิธีที่ผมใช้นั้นใช้เวลาเป็น O(x*sqrt(x)) ครับ เช่นกันครับ วิธีนี้สามารถใช้ได้กับโจทย์ข้อ 2 และข้อ 6 |
#2
|
||||
|
||||
ครับ
ที่ผมทำไป ทำแบบทื่อ ๆ โดยไม่ได้ ใช้ความรู้คณิตศาสตร์มาเกี่ยวข้องเลยครับ. คุณอานนท์ท่าทางจะเขียน C เป็นนะครับ. ผมนึกว่าจะไม่มีคนดูบ้างซะอีก |
#3
|
|||
|
|||
ทำไม complexity ไม่ใช่ O(sqrt(x)) เหรอครับ?
|
#4
|
|||
|
|||
ถ้าคำนวณตัวเดียวก็ sqrt(n)
แต่ถ้า n ตัวก็ n*sqrt(n) |
#5
|
|||
|
|||
n มันคืออะไรเหรอครับ? เห็นแต่ x?
|
|
|