Saya ingin algoritme atau kode yang sangat cepat dalam C melakukan tugas berikut: menjumlahkan semua angka dari 1 hingga N untuk bilangan bulat N tertentu, tanpa berasumsi N positif. Saya membuat perulangan dengan penjumlahan dari 1 hingga N, tetapi terlalu lambat.
Algoritme tercepat untuk menjumlahkan angka hingga N [ditutup]
comment
Pekerjaan rumah, ya...?
- person Dirk Vollmar schedule 12.04.2010
comment
Kalau itu pekerjaan rumah, saya ragu dia akan bertanya, jawabannya cukup sepele. Itu mungkin salah satu momen ketika Anda membuat kode sesuatu lalu menyadari ada rumus yang menemukan hal yang Anda inginkan.
- person ldog schedule 12.04.2010
comment
Mengingat ini adalah soal matematika diskrit standar tingkat dua, saya ragu itu pekerjaan rumah... Kecuali, tentu saja dada diam-diam adalah siswa sekolah dasar di kelas matematika dengan Gauss... B-)
- person Brian Postow schedule 12.04.2010
comment
bukankah ada thread terbaru (atau mungkin postingan blog codinghorror) tentang bagaimana programmer sebenarnya tidak perlu tahu matematika? Saya pikir pertanyaan ini adalah ilustrasi sempurna mengapa mereka perlu mengetahui matematika! (dan saya menggunakan matematika dalam arti yang dimaksudkan oleh kebanyakan orang awam, bukan dalam arti yang mencakup ilmu komputer, logika, dll)
- person rmeador schedule 13.04.2010
comment
Siapa yang memberi suara positif pada pertanyaan ini?
- person qrdl schedule 13.04.2010
comment
@qrdl: Ada yang ingin mendapatkan lencana Elektorat?
- person David Thornley schedule 13.04.2010
comment
Saya terkejut dan terkejut
- person Marko Dumic schedule 13.04.2010
comment
@qrdl Siapa yang menandainya sebagai favorit!?!?!?
- person Tom schedule 13.04.2010
comment
@Tom: Meskipun bukan saya, saya menggunakan alat favorit sebagai cara menandai postingan yang memberikan informasi yang akan berguna bagi saya di masa mendatang. Mungkin orang lain ingin mengingat trik yang digunakan dalam banyak jawaban.
- person Ponkadoodle schedule 13.04.2010
comment
@David - Orang yang mencalonkan diri sebagai Elektorat juga dapat memilih menolak. Petunjuk petunjuk.
- person Chris Lutz schedule 13.04.2010
comment
Tidakkah Anda ingin menghitung 1+1+...+1 (n kali) dengan cepat juga?
- person Alexey Malistov schedule 13.04.2010
comment
@Chris Lutz: Saya tahu, tetapi upvoting sepertinya lebih bagus dan tidak memerlukan biaya. Cara termudah untuk mendapatkan Elektorat adalah dengan memberi suara positif pada pertanyaan secara acak, yang merupakan diskusi lain yang termasuk dalam Meta.
- person David Thornley schedule 13.04.2010
Jawaban (8)
Jika N positif: int sum = N*(N+1)/2;
Jika N negatif: int tempN = -N; int sum = 1 + tempN*(tempN+1)/2 * (-1);.
person
IVlad
schedule
12.04.2010
Jika N negatif memerlukan
+ 1 di akhir. 1 + 0 + -1 + -2 = -2, bukan -3.
- person tloflin; 12.04.2010
Ups! Terima kasih, melewatkannya.
- person IVlad; 12.04.2010
@Dave: Ya, Anda harus selalu melakukan optimasi prematur karena ini benar-benar membuat perbedaan, dan kompiler tidak akan pernah cukup pintar untuk mengetahuinya dengan sendirinya. Perhatikan juga bahwa ini mungkin lebih cepat karena tidak melakukan hal yang sama (Anda ingin
>> 1).
- person erikkallen; 12.04.2010
Tidak ada penjelasan tentang bagaimana cara kerjanya? Saya akan mencobanya:
N/2 menemukan nilai rata-rata semua angka antara 0 dan N. Kita mulai dari 1, jadi ubah ke (N+1)/2. Sekarang kita sudah mempunyai nilai rata-ratanya, kita hanya perlu mengalikannya dengan banyaknya nilai pada barisan (N) (sebenarnya N-1(nilai awal)+1(1 sampai 2 berisi 2 nilai, bukan 2-1=1 ), tetapi N-1+1=N). Jadi N*((N+1)/2), dikurangi = N*(N+1)/2.
- person Ponkadoodle; 13.04.2010
@erikkallen: (suara positif untuk senyuman saya). Ditambah lagi, saya yakin perubahan yang tepat ditentukan oleh implementasi untuk data yang ditandatangani?
- person Dan; 13.04.2010
Ada juga bukti induktif yang bagus untuk hal ini, jika Anda memerlukan lebih dari sekedar demonstrasi sederhana.
- person avpx; 13.04.2010
bukankah akan lebih bagus jika kompiler diperlukan dan mampu menyimpulkan transformasi seperti itu? :)
- person Will Ness; 11.07.2014
Rumus yang Anda cari adalah bentuk yang lebih umum dari rumus yang diposting di beberapa jawaban atas pertanyaan Anda, yaitu Deret/Perkembangan Aritmatika dengan faktor selisih 1. Dari Wikipedia, berikut ini:
Rumus di atas akan menangani bilangan negatif selama m selalu lebih kecil dari n. Misalnya untuk mendapatkan jumlah dari 1 sampai -2, setel m ke -2 dan n ke 1, yaitu jumlah dari -2 ke 1. Melakukan hal ini akan menghasilkan:
(1 - -2 + 1) * (1 + -2) / 2 = 4 * -1 / 2 = -4 / 2 = -2.
itulah hasil yang diharapkan.
person
Void
schedule
12.04.2010
+1 untuk memberikan rumus umum.
- person Matthieu M.; 13.04.2010
Untuk melengkapi jawaban di atas, beginilah cara Anda membuktikan rumusnya (contoh untuk bilangan bulat positif tetapi prinsipnya sama untuk bilangan negatif atau rangkaian aritmatika apa pun seperti yang ditunjukkan oleh Void).
Cukup tulis suite dua kali seperti di bawah ini dan tambahkan angka:
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
suku ketiga dari jumlah(n..1) seharusnya n-2.
- person Ponkadoodle; 13.04.2010
+1 untuk menjelaskannya secara intuitif
- person Anurag; 13.04.2010
@wallacoloo: terima kasih. Saya mengoreksi jawabannya (dan juga kesalahan ketik lainnya).
- person kriss; 13.04.2010
@Void: terima kasih tapi saya tidak pantas, ini bukti klasik Gauss.
- person kriss; 13.04.2010
Tahukah Anda compleat hanya bisa digunakan sebagai kata sifat dan bukan kata kerja, bukan?
- person Ben Voigt; 13.04.2010
@Ben Voigt: Hanya jika Anda tidak tahu cara menggunakan kata sifat :D
- person Ponkadoodle; 13.04.2010
Untuk menangani integer overflow saya akan menggunakan fungsi berikut:
sum = (N%2) ? ( ((N+1)/2)*N ) : ( (N/2)*(N+1) );
person
Kirill V. Lyadvinsky
schedule
12.04.2010
pintar... Tapi ini masih rentan terhadap integer overflow. Anda tidak menghadapinya, hanya menundanya.
- person Ponkadoodle; 13.04.2010
Ini akan menundanya selama mungkin.
- person Kirill V. Lyadvinsky; 13.04.2010
Coba ini...
Dimana n adalah bilangan bulat maksimum yang perlu Anda jumlahkan.
Jumlahnya adalah (n*(N+1))/2
person
adengle
schedule
12.04.2010
Pernahkah Anda mendengar tentang urutan & deret? Kode 'cepat' yang anda inginkan adalah penjumlahan deret aritmatika dari 1 sampai N .. google saja .. langsung buka buku matematika anda ..
person
sp3tsnaz
schedule
13.04.2010
jika |n| cukup kecil, tabel pencarian akan menjadi yang tercepat.
atau menggunakan cache, cari terlebih dahulu cache tersebut, jika tidak dapat menemukan record maka kalkulasikan penjumlahannya dengan menggunakan n * (n + 1) / 2 (jika n positif), dan catat hasilnya ke dalam cache.
person
wenlujon
schedule
13.04.2010
person
schedule
Tapi itu hanya O(1)!
- person dancavallaro; 12.04.2010
@dancavallaro: tidak jika Anda menghitung operasi bitwise, tidak!
- person ldog; 12.04.2010
Anda selalu dapat mengkodekan nilai penjumlahan dari −32.768 hingga +32.767. Siklusnya pun lebih sedikit :D
- person Venus; 12.04.2010
Saya rasa ini tidak berfungsi dengan angka negatif. Jika N adalah -3, rumus ini menghasilkan 3 tetapi -3+-2+-1+0+1 = -5
- person Patrick Desjardins; 12.04.2010
@gmatt benar, ini sebenarnya
O(log N), kecuali Anda membatasi nilai N, dalam hal ini loop naifnya juga O(1).
- person avakar; 12.04.2010
@avakar: Saya memberi suara positif pada komentar Anda, tetapi apakah pengganda
O(log N) benar-benar ada? Wikipedia tidak mencantumkan apa pun: en.wikipedia.org/wiki/
- person erikkallen; 13.04.2010
@erikkallen, salahku, aku berpikir setidaknya
log N, seharusnya tertulis \Omega(log N).
- person avakar; 13.04.2010
Jika pemahaman saya tentang wikipedia benar, algoritma Schönhage-Strassen (yang tampaknya merupakan algoritma yang paling cepat ditemukan dan dapat digunakan secara praktis) akan memberikan kompleksitas waktu untuk masalah
O(log N log log N log log log N) ini
- person erikkallen; 13.04.2010
