Geekly articles weekly

Tugas uji Yandex

Tantangan


Tulis fungsi yang dari array input acak akan memilih semua kombinasi angka dengan jumlah 10.

Sekilas, tugasnya sederhana, yang perlu Anda lakukan hanyalah menulis rekursi dan memilah-milah semua nilai.

Atau Anda dapat menggunakan kenaikan biner, tetapi untuk mengulangi semua nilai untuk vektor jumlah panjang N, dibutuhkan 2 ^ n iterasi.

Pertama, kita memilih case khusus, misalkan array terdiri dari angka> 0. Kemudian, berdasarkan contoh ini, kita akan mengimplementasikan semua case.

LANGKAH 1


a) Pertimbangkan salah satu kasus khusus - jumlah semua elemen array <10.
Logikanya sederhana, jumlah (V) <10, lalu jumlah (V) -V [i] <jumlah, yaitu, jika jumlah kombinasi akan selalu kurang dari 10.

b) Jika jumlah (V) = 10, maka jumlah jumlah (V) -V [i] <jumlah. Hasilnya hanya satu v .

LANGKAH 2


Kami menghapus semua yang tidak perlu dari vektor

Sebagai contoh, ambil array [13, 10, 20, 13, 13, 18, 2, 9, 5, 8, 8, 9, 2, 1, 8, 16, 4, 15, 2, 2, 2, 2, 1, 5 , 5, 5].

Ini segera menunjukkan bahwa tidak masuk akal untuk mencari kombinasi jika nilainya> 10, tetapi semuanya akan segera menjadi jelas. jika kita mengurutkannya:

[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 15, 16, 18, 20 ]

Pada tahap ini, kita sudah bisa tahu pasti bahwa kita perlu menghapus semua elemen yang lebih besar dari 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]

Namun faktanya, semuanya sedikit lebih menarik. kita perlu membatasi vektor ke nilai sehingga V [0] + V [i] <= 10; di mana saya cenderung ke N; Tetapi jika V [i] = 10, maka kita tambahkan 10 ke hasilnya
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]

LANGKAH 3


Ada elemen duplikat dalam array yang sudah difilter. Jika kita mendekomposisikan vektor menjadi sub-vektor, dan menghitung jumlahnya, kita mendapatkan sesuatu seperti ini
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[5, 5, 5, 5] => 20
[8, 8, 8] => 24
[9.9] => 18

Inti dari pikiran saya adalah sedemikian rupa sehingga tidak masuk akal untuk mempertimbangkan kombinasi angka berulang jika jumlah * nilai> 10. Artinya, kita memotong vektor sampai jumlah mereka kurang dari 10, dan menambahkan yang 10 untuk hasilnya:
[1,1] => [1,1]
[2, 2, 2, 2, 2] => [2, 2, 2, 2]
[4] => [4]
[5, 5, 5, 5] => [5]
[8, 8, 8] => [8]
[9.9] => [9]

Sebagai hasil dari langkah ke-3, vektor kita adalah sebagai berikut
[1, 1, 2, 2, 2, 4, 5, 8, 9]

Seperti yang Anda lihat, ukuran vektor telah menurun dari 25 menjadi 9, ukurannya jauh lebih kecil (ingat jumlah iterasi);

Dengan angka negatif


Ini sedikit lebih rumit. kami akan menganggap bahwa kami menerapkan fungsi menemukan kombinasi untuk vektor yang diurutkan positif, berdasarkan batasan sebelumnya.
comb (arr, sum), di mana jumlah adalah jumlah yang diperlukan, arr adalah vektor yang diurutkan dari angka positif

Misalnya, ambil vektor:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12, , -10, 9]

1. Hancurkan vektor
A = hanya nilai positif
B = hanya nilai negatif
Dan lihat juga apakah kita memiliki nilai = 0

2. Sortir
Sortir vektor (naik positif, turun negatif)

Periksa kasus khusus untuk angka positif (LANGKAH 1)

3. Verifikasi positif
Periksa nilai-nilai positif
sisir (B, 10)

3. Periksa negatif
buat kombinasi semua angka negatif, tetapi dengan batasan:

(jumlah elemen modulo) <(jumlah semua positif) + 10
kami menemukan kombinasi untuk jumlah referensi BARU (jumlah elemen modulo + 10)

4. Kesetaraan 0
Jika vektor sumber memiliki nilai 0, maka kami menambahkan semua kombinasi + 0 ke hasilnya;

Sebagai hasil dari keterbatasan seperti itu, rata-rata, ketika menguji nilai dengan array 28 dan 1000 tes panjang, kenaikan waktu hampir 42%

Berhati-hatilah agar tidak terlihat gugup. Penulis tidak bertanggung jawab atas penderitaan moral.
function combine(arr, etalon = 10) { //--------------------------------------------// //------------- helpers --------------------// //    // Create binnary array function createBin(length) { let bin = []; for (let i = 0; i < length; i++) { bin[i] = false; } return bin; } //   1 //Binnary add 1 bit function binAddBit(bin, i = 0) { if (i >= bin.length) { return null; } if (bin[i] == false) { bin[i] = true; return bin; } else { bin[i] = false; i++; return binAddBit(bin, i); } } function iniq(arr) { let result = []; let object = {}; arr.forEach(vector => { value = vector.sort(function(a, b) { return a - b }); key = value.join(','); object[key] = value; }); for (var key in object) { result.push(object[key]); } return result; } //   // : //       //       //       function _combine(arr, sum = 10) { let result = []; //   if (arr[0] > sum) return []; if (arr[0] == sum) return [ [sum] ]; //1.   let $aKey = {}; let $a = []; let $sum = 0; //    $aKey[arr[0]] = arr[0]; $a.push(arr[0]); $sum += arr[0]; let $eqSum = false; for (let i = 1; i < arr.length; i++) { if ((arr[i] + arr[0]) <= sum) { //-----------------------------// // count*element < sum $aKey[arr[i]] = $aKey[arr[i]] != undefined ? $aKey[arr[i]] += arr[i] : arr[i]; if ($aKey[arr[i]] < sum) { $a.push(arr[i]); $sum += arr[i]; } //-----------------------------// //-----------------------------// // count*element = sum if ($aKey[arr[i]] === sum) { let $res = []; for (let j = 0; j < (sum / arr[i]); j++) { $res.push(arr[i]); } result.push($res); } //-----------------------------// } if (arr[i] == sum) { $eqSum = true; } } if ($eqSum) { result.push([sum]); } if ($sum < sum) return result; if ($sum == sum) { result.push($a); return result; } //   let bin = createBin($a.length); while (change = binAddBit(bin)) { let $sum = 0; let $comb = []; for (let i = 0; i < change.length; i++) { if (change[i] == false) continue; $sum += $a[i]; if ($sum > sum) break; // exit in accumulate $comb.push($a[i]); if ($sum == sum) { result.push($comb); } } } return result; } //------------- helpers --------------------// //--------------------------------------------// let result = []; //         //   -   let zero = false; //       let posetive = []; let negative = []; let sumPosetive = 0; arr.forEach(element => { if (element === 0) { zero = true; } if (element < 0) { negative.push(element); } if (element > 0) { posetive.push(element); sumPosetive += element; } }); //   ( ) posetive.sort(function(a, b) { return a - b }); negative.sort(function(a, b) { return b - a }); //       ,  //       if (sumPosetive < etalon) return []; //       if (sumPosetive == etalon) { result.push(posetive); if (zero) { let _clone = posetive.slice(); _clone.push(0); result.push(_clone); } return result; } //      ; result = result.concat(_combine(posetive, etalon)); // SUPPLE -          combinPosetiveLim negative = negative.filter(function(value) { return -value <= (sumPosetive + etalon); }); //    (  ) let bin = createBin(negative.length); //   while (changeBin = binAddBit(bin)) { let sum = etalon; let vector = []; //      for (let i = 0; i < changeBin.length; i++) { if (changeBin[i] == false) continue; sum -= negative[i]; vector.push(negative[i]); } if (sum > (sumPosetive + etalon)) continue; let lines = _combine(posetive, sum); lines.forEach(value => { result.push(vector.concat(value)); }); } //    0 if (zero) { result.forEach(item => { let _clone = item.slice(); _clone.push(0); result.push(_clone); }); } result = iniq(result); return result; }

Source: https://habr.com/ru/post/id460923/

More articles:


All Articles