ฉันต้องการอัลกอริธึมหรือโค้ดที่เร็วใน C จริงๆ เพื่อทำงานต่อไปนี้: รวมตัวเลขทั้งหมดตั้งแต่ 1 ถึง N สำหรับจำนวนเต็ม N ที่กำหนดใดๆ โดยไม่ถือว่า N เป็นบวก ฉันสร้างการวนซ้ำโดยรวมจาก 1 ถึง N แต่มันช้าเกินไป
อัลกอริธึมที่เร็วที่สุดในการรวมตัวเลขสูงสุด N [ปิด]
comment
การบ้านเอ๊ะ...?
- person Dirk Vollmar schedule 12.04.2010
comment
ถ้าเป็นการบ้านฉันสงสัยว่าเขาจะถามคำตอบนั้นค่อนข้างจะเล็กน้อย อาจเป็นหนึ่งในช่วงเวลาที่คุณเขียนโค้ดบางอย่างขึ้นมาแล้วพบว่ามีสูตรที่จะค้นหาสิ่งที่คุณต้องการ
- person ldog schedule 12.04.2010
comment
เนื่องจากนี่เป็นปัญหาคณิตศาสตร์แยกระดับนักเรียนปีที่สองมาตรฐาน ฉันสงสัยว่าเป็นการบ้าน... เว้นแต่ว่า ดาด้าแอบเป็นนักเรียนชั้นประถมศึกษาในชั้นเรียนคณิตศาสตร์กับเกาส์... ข-)
- person Brian Postow schedule 12.04.2010
comment
ไม่มีกระทู้ล่าสุด (หรืออาจจะเป็นโพสต์บล็อกการเขียนโค้ดสยองขวัญ) เกี่ยวกับวิธีที่โปรแกรมเมอร์ไม่จำเป็นต้องรู้คณิตศาสตร์จริงๆเหรอ? ฉันคิดว่าคำถามนี้เป็นตัวอย่างที่สมบูรณ์แบบว่าทำไมพวกเขาถึงต้องรู้คณิตศาสตร์! (และฉันใช้คณิตศาสตร์ในความหมายที่คนทั่วไปส่วนใหญ่หมายถึง ไม่ใช่ในแง่ที่ครอบคลุมถึงวิทยาการคอมพิวเตอร์ ตรรกะ ฯลฯ)
- person rmeador schedule 13.04.2010
comment
ใครโหวตคำถามนี้?
- person qrdl schedule 13.04.2010
comment
@qrdl: มีใครอยากได้ตราผู้มีสิทธิเลือกตั้งบ้างไหม?
- person David Thornley schedule 13.04.2010
comment
ฉันตกใจและตกใจ
- person Marko Dumic schedule 13.04.2010
comment
@qrdl ใครทำเครื่องหมายว่าเป็นรายการโปรด !?!?!?
- person Tom schedule 13.04.2010
comment
@ทอม: แม้ว่าจะไม่ใช่ฉัน แต่ฉันใช้เครื่องมือโปรดนี้เป็นวิธีบุ๊กมาร์กโพสต์ที่ให้ข้อมูลซึ่งจะเป็นประโยชน์กับฉันในอนาคต บางทีอาจมีคนอื่นต้องการจำเคล็ดลับที่ใช้ในคำตอบหลายข้อ
- person Ponkadoodle schedule 13.04.2010
comment
@David - คนที่ไปรับการเลือกตั้งสามารถลงคะแนน ลง ได้เช่นกัน คำใบ้คำใบ้.
- person Chris Lutz schedule 13.04.2010
comment
คุณไม่ต้องการคำนวณ 1+1+...+1 (n ครั้ง) อย่างรวดเร็วด้วยใช่ไหม
- person Alexey Malistov schedule 13.04.2010
comment
@Chris Lutz: ฉันรู้ แต่การโหวตดูเหมือนจะดีกว่าและไม่เสียค่าใช้จ่ายในการทำซ้ำ วิธีที่ง่ายที่สุดในการรับการเลือกตั้งคือการสุ่มโหวตเห็นด้วย ซึ่งเป็นอีกการสนทนาที่อยู่ใน Meta
- person David Thornley schedule 13.04.2010
คำตอบ (8)
ถ้า N เป็นบวก: int sum = N*(N+1)/2;
ถ้า N เป็นค่าลบ: int tempN = -N; int sum = 1 + tempN*(tempN+1)/2 * (-1);
person
IVlad
schedule
12.04.2010
ถ้า N เป็นลบ ต้องมี
+ 1 ต่อท้าย 1 + 0 + -1 + -2 = -2 ไม่ใช่ -3
- person tloflin; 12.04.2010
อ๊ะ! ขอบคุณ พลาดแล้ว
- person IVlad; 12.04.2010
@Dave: ใช่ คุณควรดำเนินการปรับให้เหมาะสมก่อนเวลาอันควรเสมอ เพราะมันสร้างความแตกต่างได้จริงๆ และคอมไพเลอร์จะไม่ฉลาดพอที่จะคิดออกด้วยตัวเอง โปรดทราบว่าอาจเร็วกว่าเนื่องจากไม่ได้ทำสิ่งเดียวกัน (คุณต้องการ
>> 1)
- person erikkallen; 12.04.2010
ไม่มีคำอธิบายว่า วิธี ทำงานอย่างไร ฉันจะลองดู:
N/2 ค้นหาค่าเฉลี่ยของตัวเลขทั้งหมดระหว่าง 0 ถึง N เราเริ่มต้นที่ 1 ดังนั้นให้เปลี่ยนเป็น (N+1)/2 ตอนนี้เรามีค่าเฉลี่ยแล้ว เราแค่ต้องคูณด้วยจำนวนค่าในลำดับ (N) (จริงๆ แล้ว N-1(ค่าเริ่มต้น)+1(1 ถึง 2 มี 2 ค่า ไม่ใช่ 2-1=1 ) แต่ N-1+1=N) ดังนั้น N*((N+1)/2) ลดลง = N*(N+1)/2
- person Ponkadoodle; 13.04.2010
@erikkallen: (โหวตให้กับรอยยิ้มของฉัน) นอกจากนี้ฉันเชื่อว่าการเปลี่ยนแปลงที่ถูกต้องคือการกำหนดการใช้งานสำหรับข้อมูลที่ลงนามหรือไม่
- person Dan; 13.04.2010
มีข้อพิสูจน์เชิงอุปนัยที่ดีเช่นกัน ในกรณีที่คุณต้องการมากกว่าการสาธิตง่ายๆ
- person avpx; 13.04.2010
จะดีกว่าไหมหากจำเป็นต้องใช้คอมไพเลอร์และ สามารถ อนุมานการเปลี่ยนแปลงดังกล่าวได้ :)
- person Will Ness; 11.07.2014
สูตรที่คุณกำลังมองหาคือรูปแบบทั่วไปของสูตรที่โพสต์ในหลายคำตอบสำหรับคำถามของคุณ ซึ่งก็คือ ชุดเลขคณิต/ความก้าวหน้า ด้วยปัจจัย ผลต่าง ที่ 1 จาก Wikipedia มีดังต่อไปนี้:
สูตรข้างต้นจะจัดการกับจำนวนลบตราบใดที่ m น้อยกว่า n เสมอ ตัวอย่างเช่น หากต้องการหาผลรวมตั้งแต่ 1 ถึง -2 ให้ตั้งค่า m เป็น -2 และ n เป็น 1 กล่าวคือ ผลรวมจาก -2 ถึง 1 การทำเช่นนี้ส่งผลให้:
(1 - -2 + 1) * (1 + -2) / 2 = 4 * -1 / 2 = -4 / 2 = -2.
ซึ่งเป็นผลที่คาดว่าจะได้รับ
person
Void
schedule
12.04.2010
+1 ให้สูตรทั่วไปครับ
- person Matthieu M.; 13.04.2010
เพียงเพื่อตอบคำถามข้างต้นให้สมบูรณ์ นี่คือวิธีที่คุณพิสูจน์สูตร (ตัวอย่างสำหรับจำนวนเต็มบวก แต่หลักการจะเหมือนกันสำหรับค่าลบหรือชุดเลขคณิตใดๆ ตามที่ Void ชี้ให้เห็น)
เพียงเขียนชุดสองครั้งตามด้านล่างแล้วบวกตัวเลข:
1+ 2+ 3+ ... n-2+ n-1+ n = sum(1..n) : n terms from 1 to n
+ n+ n-1+ n-2+ ... 3+ 2+ 1 = sum(n..1) : the same n terms in reverse order
--------------------------------
n+1+ n+1+ n+1+ ... n+1+ n+1+ n+1 = 2 * sum(1..n) : n times n+1
n * (n+1) / 2 = sum(1..n)
person
kriss
schedule
12.04.2010
งวดที่สามของผลรวม (n..1) ควรเป็น n-2
- person Ponkadoodle; 13.04.2010
+1 สำหรับการอธิบายอย่างสังหรณ์ใจ
- person Anurag; 13.04.2010
@wallacoloo: ขอบคุณ ฉันแก้ไขคำตอบแล้ว (และยังพิมพ์ผิดอีก)
- person kriss; 13.04.2010
@Void: ขอบคุณ แต่ฉันไม่มีบุญ มันเป็นข้อพิสูจน์คลาสสิกของ Gauss
- person kriss; 13.04.2010
คุณรู้ไหมว่า complet สามารถใช้เป็นคำคุณศัพท์เท่านั้นไม่ใช่คำกริยาใช่ไหม?
- person Ben Voigt; 13.04.2010
@Ben Voigt: เฉพาะในกรณีที่คุณไม่รู้วิธีกริยาคำคุณศัพท์ :D
- person Ponkadoodle; 13.04.2010
เพื่อจัดการกับจำนวนเต็มล้น ฉันจะใช้ฟังก์ชันต่อไปนี้:
sum = (N%2) ? ( ((N+1)/2)*N ) : ( (N/2)*(N+1) );
person
Kirill V. Lyadvinsky
schedule
12.04.2010
ฉลาด... แต่นี่ ยังคง เสี่ยงต่อการล้นของจำนวนเต็ม คุณไม่ได้กำลังจัดการกับมัน เพียงแต่ชะลอมันออกไป
- person Ponkadoodle; 13.04.2010
มันจะหน่วงเวลาให้นานที่สุด
- person Kirill V. Lyadvinsky; 13.04.2010
ลองสิ่งนี้...
โดยที่ n คือจำนวนเต็มสูงสุดที่คุณต้องหาผลรวม
ผลรวมคือ (n*(N+1))/2
person
adengle
schedule
12.04.2010
คุณเคยได้ยินเกี่ยวกับลำดับและซีรีส์บ้างไหม? รหัส 'เร็ว' ที่คุณต้องการคือผลรวมของชุดเลขคณิตตั้งแต่ 1 ถึง N .. google it .. infact เปิดหนังสือคณิตศาสตร์ของคุณ ..
person
sp3tsnaz
schedule
13.04.2010
ถ้า |n| มีขนาดเล็กพอ ตารางการค้นหาจะเป็นตารางที่เร็วที่สุด
หรือใช้แคช ค้นหาแคชก่อน หากไม่พบบันทึก ให้คำนวณผลรวมโดยใช้ n * (n + 1) / 2(ถ้า n เป็นบวก) แล้วบันทึกผลลัพธ์ลงในแคช
person
wenlujon
schedule
13.04.2010
person
schedule
แต่นั่นเป็นเพียง O(1)!
- person dancavallaro; 12.04.2010
@dancavallaro: ไม่ใช่ถ้าคุณนับการดำเนินการระดับบิตมันไม่ใช่!
- person ldog; 12.04.2010
คุณสามารถฮาร์ดโค้ดค่าผลรวมของ −32,768 ถึง +32,767 ได้ตลอดเวลา รอบน้อยลง :D
- person Venus; 12.04.2010
ฉันไม่คิดว่ามันใช้ได้กับจำนวนลบ ถ้า N คือ -3 สูตรนี้ให้ 3 แต่ -3+-2+-1+0+1 = -5
- person Patrick Desjardins; 12.04.2010
@gmatt ถูกต้อง นี่คือ
O(log N) จริงๆ เว้นแต่คุณจะจำกัดค่าของ N ซึ่งในกรณีนี้ naïve loop จะเป็น O(1) เช่นกัน
- person avakar; 12.04.2010
@avakar: ฉันโหวตความคิดเห็นของคุณแล้ว แต่มีตัวคูณ
O(log N) อยู่จริงหรือไม่ Wikipedia ไม่แสดงรายการใดๆ: en.wikipedia.org/wiki/
- person erikkallen; 13.04.2010
@erikkallen แย่จัง ฉันคิดว่าอย่างน้อย
log N ก็ควรจะพูดว่า \Omega(log N)
- person avakar; 13.04.2010
หากความเข้าใจของฉันเกี่ยวกับวิกิพีเดียถูกต้อง อัลกอริธึมSchönhage-Strassen (ซึ่งดูเหมือนจะเป็นอัลกอริธึมที่ค้นพบได้เร็วที่สุดและใช้งานได้จริง) จะให้เวลาที่ซับซ้อนสำหรับปัญหานี้ที่
O(log N log log N log log log N)
- person erikkallen; 13.04.2010
