n
Angka yang diberikan dalam array (Anda tidak dapat menganggap itu bilangan bulat), saya ingin menghitung produk dari semua subset ukuran n-1
.
Anda dapat melakukan ini dengan mengalikan semua angka bersama dan kemudian membaginya dengan masing-masing secara berurutan, selama tidak ada angka yang nol. Namun, seberapa cepat Anda dapat melakukan ini tanpa divisi?
Jika Anda tidak mengizinkan pembagian, berapakah jumlah minimum operasi aritmatika (mis. Penggandaan dan penambahan) yang diperlukan untuk menghitung produk dari semua himpunan bagian ukuran n-1?
Jelas Anda bisa melakukannya dalam (n-1)*n
multiplikasi.
Untuk memperjelas, output adalah n
produk yang berbeda dan satu-satunya operasi selain dari membaca dan menulis ke memori diperbolehkan adalah perkalian, penambahan dan pengurangan.
Contoh
Jika input memiliki tiga angka 2,3,5
, maka outputnya adalah tiga angka 15 = 3*5
, 10 = 2*5
dan 6 = 2*3
.
Kriteria menang
Jawaban harus memberikan formula yang tepat untuk jumlah operasi aritmatika yang akan digunakan oleh kode mereka n
. Untuk membuat hidup lebih sederhana, saya hanya akan memasukkan n = 1000
formula Anda untuk menilai nilainya. Semakin rendah semakin baik.
Jika terlalu sulit untuk menghasilkan formula yang tepat untuk kode Anda, Anda bisa menjalankannya n = 1000
dan menghitung operasi aritmatika dalam kode. Namun formula yang tepat adalah yang terbaik.
Anda harus menambahkan skor n=1000
Anda ke jawaban Anda untuk perbandingan yang mudah.
sumber
+
pada indeks dihitung? Jika ini masalahnya, apakah array indexing juga dihitung? (karena itu adalah gula sintaksis untuk penambahan dan dereferencing).(n-1)*n
multiplikasi Maksud Anda(n-2)*n
, bukan?Jawaban:
Operasi Python, 3 (n-2), skor = 2994
Array
left
dan masing-masingright
berisi produk terakumulasi dari array dari kiri dan dari kanan.EDIT: Bukti bahwa 3 (n-2) adalah jumlah operasi optimal yang diperlukan untuk n> = 2, jika kita hanya menggunakan perkalian.
Kami akan melakukannya dengan induksi; oleh algoritma di atas, kita hanya perlu membuktikan bahwa untuk n> = 2, 3 (n-2) adalah batas bawah pada jumlah perkalian yang dibutuhkan.
Untuk n = 2, kita membutuhkan paling tidak 0 = 3 (2-2) perkalian, sehingga hasilnya sepele.
Misalkan n> 2, dan anggap untuk elemen n - 1, kita membutuhkan setidaknya 3 (n-3) perkalian. Pertimbangkan solusi untuk n elemen dengan perkalian k. Sekarang, kami menghapus elemen terakhir seolah-olah 1, dan menyederhanakan semua perkalian secara langsung olehnya. Kami juga menghapus perkalian yang mengarah ke produk dari semua elemen lain, karena yang satu tidak diperlukan karena tidak pernah dapat digunakan sebagai nilai perantara untuk mendapatkan produk n-2 dari elemen lain, karena pembagian tidak diperbolehkan. Ini meninggalkan kita dengan l perkalian, dan solusi untuk elemen n - 1.
Dengan hipotesis induksi, kita memiliki l> = 3 (n-3).
Sekarang, mari kita lihat berapa banyak perkalian yang dihapus. Salah satunya adalah yang mengarah ke produk dari semua elemen kecuali yang terakhir. Selain itu, elemen terakhir digunakan langsung dalam setidaknya dua perkalian: jika digunakan hanya dalam satu, maka itu digunakan ketika mengalikan dengan hasil antara yang terdiri dari beberapa produk dari elemen lain; katakanlah, tanpa kehilangan sifat umum, hasil antara ini termasuk elemen pertama dalam produk. Kemudian, tidak ada cara untuk mendapatkan produk dari semua elemen kecuali yang pertama, karena setiap produk yang mengandung elemen terakhir adalah elemen terakhir, atau mengandung elemen pertama.
Dengan demikian, kita memiliki k> = l + 3> = 3 (n-2), membuktikan teorema yang diklaim.
sumber
f l = zipWith (*) (scanl (*) 1 l) (scanr (*) 1 $ tail l)
.Haskell , skor 2994
Cobalah online!
Katakanlah kita diberi daftar
[a,b,c,d,e,f,g,h]
. Kami pertama kali mengelompokkannya menjadi beberapa[[a,b],[c,d],[e,f],[g,h]]
. Kemudian, kami mengulang daftar setengah ukuranpairs
produk mereka untuk mendapatkansubresults
Jika kita mengambil elemen pertama
(c*d)*(e*f)*(g*h)
, dan kalikan denganb
dana
masing-masing, kita mendapatkan produk dari semua tapia
dan semua tapib
. Melakukan ini untuk setiap pasangan dan hasil rekursif dengan pasangan itu hilang, kami mendapatkan hasil akhir. Kasing panjang ganjil secara khusus ditangani dengan membiarkan elemen aneh dilewatkan tidak berpasangan ke langkah rekursif, dan produk dari elemen yang tersisa dikembalikan adalah produk tanpa itu.Jumlah perkalian
t(n)
adalahn/2
untuk produk pasangan,t(n/2)
untuk panggilan rekursif, dan lainnyan
untuk produk dengan elemen individual. Ini memberit(n) = 1.5 * n + t(n/2)
anehn
. Menggunakan hitungan yang lebih tepat untukn
mengalikan ganjil dan mengabaikan dengan1
untuk kasus dasar memberikan skor2997
untukn=1000
.sumber
products_but_one'
dapat menghindarinya dengan mengembalikan sesuatu dengan panjang yang benar.1
yang bebas untuk berkembang biak. Saya pikir padding 1 tidak mempengaruhi hal-hal, tetapi saya membersihkan algoritma saya untuk tidak menggunakannya.float
.Haskell , skor 9974
Cobalah online!
Strategi memecah-dan-menaklukkan, sangat mirip dengan jenis gabungan. Tidak melakukan pengindeksan.
Fungsi
partition
membagi daftar menjadi dua bagian yang sama dengan mungkin dengan menempatkan elemen bergantian di sisi yang berlawanan dari partisi. Kami menggabungkan hasil secara rekursif(p,r)
untuk setiap bagian, denganr
daftar produk-dengan-satu-hilang, danp
produk keseluruhan.Untuk output untuk daftar lengkap, elemen yang hilang harus berada di salah satu bagian. Produk dengan elemen yang hilang itu adalah produk satu-hilang untuk separuhnya, dikalikan dengan produk lengkap untuk setengah lainnya. Jadi, kami mengalikan setiap produk dengan satu yang hilang dengan produk lengkap dari setengah lainnya dan membuat daftar hasilnya
map(*p1)r2 ++ map(*p2)r1)
. Ini membutuhkann
multiplikasi, di manan
panjangnya. Kita juga perlu membuat produk lengkap barup1*p2
untuk penggunaan di masa mendatang, dengan biaya 1 kali lipat lebih banyak.Hal ini memberikan rekursi umum untuk untuk jumlah operasi
t(n)
dengann
bahkan:t(n) = n + 1 + 2 * t(n/2)
. Yang aneh mirip, tetapi salah satu sublists1
lebih besar. Melakukan rekursi, kita mendapatkann*(log_2(n) + 1)
multiplikasi, meskipun perbedaan ganjil / genap mempengaruhi nilai pastinya. Nilai-nilai hinggat(3)
ditingkatkan dengan tidak mengalikan dengan1
dengan mendefinisikan varian(%)
dari(*)
yang shortcut_*1
atau1*_
kasus.Ini memberikan
9975
multiplikasi untukn=1000
. Saya percaya kemalasan Haskell berarti produk keseluruhan yang tidak digunakan di lapisan luar tidak dihitung9974
; jika saya salah, saya bisa menghilangkannya secara eksplisit.sumber
n = 1000
dan hitung operasi aritmatika dalam kode.9974
dan tidak9975
memperbanyak untukn = 1000
(dalam hal menghitung keseluruhan produk di lapisan luar). Apakah Anda memasukkan1
dalam input yang Anda gunakan untuk mengujinya?trace
dariDebug.Trace
dengan| trace "call!" False = undefined
penjaga menangkap semua , saya pikir. Tapi ini menggunakan diunsafePerformIO
bawah tenda, jadi itu tidak benar-benar perbaikan.Haskell , skor 2994
Cobalah online!
Bagaimana itu bekerja
Ini adalah versi yang dibersihkan dari algoritma xnor yang menangani kasus aneh dengan cara yang lebih mudah (edit: sepertinya xnor telah membersihkannya dengan cara yang sama):
[a, b, c, d, e, f, g] ↦
[a, bc, de, fg] ↦
[(bc) (de) (fg), a (de) (fg), a (bc) ( fg), a (bc) (de)] dengan rekursi ↦
[(bc) (de) (fg), a (de) (fg) c, a (de) (fg) b, a (bc) (fg) e, a (bc) (fg) d, a (bc) (de) g, a (bc) (de) f]
[a, b, c, d, e, f, g, h] ↦
[ab, cd, ef, gh] ↦
[(cd) (ef) (gh), (ab) (ef) (gh), ( ab) (cd) (gh), (ab) (cd) (ef)] dengan rekursi ↦
[(cd) (ef) (gh) b, (cd) (ef) (gh) a, (ab) (ef ) (gh) d, (ab) (ef) (gh) c, (ab) (cd) (gh) f, (ab) (cd) (gh) e, (ab) (cd) (ef) h, (ab) (cd) (ef) g].
sumber
O (n log n) operasi, skor = 9974
Bekerja dengan pohon biner.
Python
Ini juga memerlukan operasi penambahan daftar, dan beberapa aritmatika pada angka yang bukan nilai input; tidak yakin apakah itu diperhitungkan. The
mul
fungsi di sana untuk menyelamatkan n operasi untuk kasus dasar, untuk menghindari pemborosan mereka dengan mengalikan dengan 1. Dalam hal apapun, ini adalah (n log n) O operasi. Formula yang tepat, jika hanya menghitung operasi aritmatika pada nomor masukan, denganj = floor(log_2(n))
:j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2
.Terima kasih kepada @xnor karena telah menghemat satu operasi dengan ide tidak menghitung produk luar!
Bagian terakhir adalah mengeluarkan produk sesuai dengan jangka waktu yang hilang.
sumber
n = 1000
dan hitung operasi aritmatika dalam kode.p[i] = p[i + i] * p[i + i+1]
tidak dihitungn log2 n + n
operasi (yaitu O (nlogn) btwp[i] = p[i + i] * p[i + i + 1]
harus disimpan oleh optimisasi multiplikasi. Saya mungkin menghitung terlalu banyak.O ((n-2) * n) = O (n 2 ): Solusi Sepele
Ini hanya solusi sepele yang mengalikan masing-masing himpunan bagian:
Python
Perhatikan bahwa ini juga membutuhkan
n
operasi penambahan daftar; tidak yakin apakah itu diperhitungkan. Jika itu tidak diizinkan, makaproduct(array[:index] + array[index + 1:])
dapat diganti menjadiproduct(array[:index]) * product(array[index + 1:])
, yang mengubah rumus menjadiO((n-1)*n)
.sumber
product
fungsi AndaO(n)
? satu untuk setiap elemen dalam array (walaupun ini dapat dengan mudah diubah menjadiO(n-1)
)Python, 7540
Strategi penggabungan tripartit. Saya pikir saya bisa melakukan lebih baik dari ini, dengan penggabungan yang belum besar. Ini O (n log n).
EDIT: Memperbaiki salah perhitungan.
Fungsi yang relevan adalah
missing_products
, yang memberikan keseluruhan produk dan semua yang memiliki elemen yang hilang.sumber
tri_merge
? Anda juga dapat mengganti2 * split_size + ...
ditri_partition
dengansplit_size + split_size + ...
.dc, skor 2994
Saya mengasumsikan bahwa perbandingan integer
z1=
(yang mengakhiri rekursi ketika kita mencapai nilai terakhir) adalah gratis. Ini setara dengan sukaforeach
dalam bahasa lain.Demonstrasi
Demo dengan input besar dan kecil:
sumber
C ++, skor: 5990, O ([2NlogN] / 3)
Implementasi ini menggunakan tabel pencarian pohon biner. Implementasi pertama saya adalah O (NlogN), tetapi optimasi menit terakhir, yang mencari produk dari semua elemen array minus sepasang, + 2 perkalian disimpan hari. Saya pikir ini masih bisa dioptimalkan sedikit lebih jauh, mungkin 16% lagi ...
Saya telah meninggalkan beberapa jejak debugging, hanya karena lebih mudah untuk menghapusnya daripada menulis ulang mereka :)
[Sunting] kompleksitas sebenarnya diukur pada O ([2NlogN] / 3) untuk 100. Ini sebenarnya sedikit lebih buruk daripada O (NlogN) untuk set kecil, tetapi cenderung ke arah O ([NlogN] / 2) ketika array tumbuh sangat besar O (0,57.NlogN) untuk satu set 1 juta elemen.
Saya menambahkan algoritma @ nore, untuk kelengkapan. Sangat bagus, dan tercepat.
sumber