Dalam masalah pompa bensin kita diberi nnn kota {0,…,n−1}{0,…,n−1}\{ 0, \ldots, n-1 \} dan jalan di antara mereka. Setiap jalan memiliki panjang dan setiap kota menentukan harga bahan bakar. Satu unit jalan menghabiskan satu unit bahan bakar. Tujuan kami adalah beralih dari sumber ke tujuan dengan...
Saya mencoba mereproduksi jaringan sintetis (grafik) yang dijelaskan dalam beberapa makalah. Disebutkan bahwa model Barabasi-Albert digunakan untuk membuat "jaringan bebas skala dengan distribusi derajat hukum-daya, ".PA(k)∝k−λPA(k)∝k−λP_A(k) ∝ k^{-λ} PAPAP_A adalah distribusi probabilitas yang...
Pertanyaan saya ditujukan kepada mereka yang peduli dengan algoritma biologi komputasi. Saya akan mengambil kursus bioinformatika musim gugur ini; Masalahnya, bagaimanapun, adalah bahwa saya memiliki terlalu sedikit latar belakang dalam biologi dan kimia untuk merasa siap untuk siklus lection (saya...
Meminimalkan deterministic finite automata (DFAs) adalah masalah yang telah dipelajari secara menyeluruh dalam literatur, dan beberapa algoritma telah diusulkan untuk menyelesaikan masalah berikut: Dengan DFA , hitung DFA minimal yang sesuai yang menerima bahasa yang sama dengan . Sebagian besar...
Mengingat array bilangan ≤ k , di mana k adalah konstanta, saya ingin jawaban dalam O ( 1 ) query dalam bentuk: "berapa kali m muncul dalam array antara indeks i dan j "?a1,…,ana1,…,ana_1,\ldots,a_n≤k≤k\leq kkkkO(1)O(1)O(1)mmmiiijjj Array harus preprocessed dalam waktu linier. Khususnya saya ingin...
Pemrograman dinamis dengan sejumlah besar masalah. Jadi saya mencoba menyelesaikan masalah ini dari Interview Street: Grid Walking (Nilai 50 poin) Anda berada di grid NNN dimensi pada posisi (x1,x2,…,xN)(x1,x2,…,xN)(x_1,x_2,\dots,x_N) . Dimensi grid adalah
Apakah "secara induktif" dan "secara rekursif" berarti sangat mirip? Misalnya, jika ada algoritma yang menentukan vektor n-dim dengan menentukan komponen k +1 pertama berdasarkan komponen k pertama yang telah ditentukan, dan diinisialisasi dengan komponen pertama, akankah Anda menyebutnya bekerja...
Selama wawancara untuk posisi pengembang Java, saya ditanya hal berikut: Tulis fungsi yang membutuhkan dua params: String yang mewakili dokumen teks dan bilangan bulat yang menyediakan jumlah item untuk dikembalikan. Menerapkan fungsi sedemikian rupa sehingga mengembalikan daftar...
Saya seorang siswa CS awal dan saya belajar algoritma. Saya mendengar bahwa bahkan dengan komputer kuantum, algoritma pengurutan umum tidak akan pernah lebih baik daripada waktu . Namun, saya juga tahu bahwa algoritma anjak piutang akan jauh lebih cepat. Secara umum, algoritma seperti apa yang akan...
Katakanlah kita memiliki 10 orang, masing-masing dengan daftar buku favorit. Untuk orang tertentu X, saya ingin menemukan subset khusus dari buku X yang hanya disukai oleh X, yaitu tidak ada orang lain yang menyukai semua buku dalam subset khusus X. Saya menganggap subset khusus ini sebagai "sidik...
Pertimbangkan grafik terarah di mana seseorang dapat secara dinamis menambahkan tepi dan membuat beberapa pertanyaan tertentu.GGG Contoh: hutan disjoint-set Pertimbangkan serangkaian pertanyaan berikut: arrow(u, v) equiv(u, v) find(u) yang pertama menambahkan panah ke grafik, yang kedua...
Apa yang kita ketahui adalah bahwa π tidak terbatas dan sangat mungkin mengandung string setiap digit string yang mungkin ( urutan disjungtif ). Saya baru-baru ini melihat beberapa prototipe πfs yang mengasumsikan bahwa setiap file yang Anda buat (atau orang lain) atau Anda akan buat, itu sudah...
Ini adalah semacam pertanyaan jarak edit, dan sangat mudah. Saya benar-benar mati otak tentang hal ini dan tidak bisa mengetahuinya sejauh ini. Diberikan serangkaian angka, mis [3, 1, 1, 1] Bagaimana cara yang paling efisien mengubah semua angka menjadi angka yang sama, dengan jumlah minimum...
Apakah ada cara untuk menghitung ukuran pencocokan maksimum dalam grafik bipartit tak tertimbang lebih efisien (mis. Lebih cepat) daripada menghitung pencocokan maksimum? Ini adalah pukulan panjang tetapi seringkali merupakan masalah yang menarik untuk menghindari perhitungan yang dibuang...
Saya memiliki dua set poin dalam bidang 2 dimensi. Saya ingin menemukan pasangan terdekat dari titik s , t sehingga s ∈ S , t ∈ T , dan jarak Euclidean antara s , t sekecil mungkin. Seberapa efisien hal ini dapat dilakukan? Bisakah itu dilakukan dalam waktu O ( n log n ) , di mana n = | S | + | T |...
Ingin memperbaiki pos ini? Berikan jawaban terinci untuk pertanyaan ini, termasuk kutipan dan penjelasan mengapa jawaban Anda benar. Jawaban tanpa detail yang cukup dapat diedit atau dihapus. Saya ditugaskan membangun perpustakaan buku tentang algoritma untuk perusahaan...
Angka Fibonacci dapat dihitung dalam waktu linier menggunakan pengulangan berikut:nnn def fib(n): i, j = 1, 1 for k in {1...n-1}: i, j = j, i+j return i Angka Fibonacci juga dapat dihitung sebagai [ φ n / √nnn. Namun, ini memiliki masalah dengan masalah pembulatan bahkan untukn yangrelatif...
Ditutup . Pertanyaan ini didasarkan pada pendapat . Saat ini tidak menerima jawaban. Ingin meningkatkan pertanyaan ini? Perbarui pertanyaan sehingga dapat dijawab dengan fakta dan kutipan dengan mengedit posting ini . Ditutup 4 tahun yang lalu . Saya...
Diberikan dua vektor bilangan bulat dengan panjang yang mungkin tidak sama, bagaimana saya bisa menentukan hasil maksimum dari akumulasi memilih maksimum antara pasangan angka yang sesuai antara dua vektor dengan nol tambahan dimasukkan ke dalam vektor yang lebih pendek untuk menebus perbedaan...
Bagaimana Anda mendeteksi secara algoritmik untuk foto tertentu apakah matahari bersinar ketika foto itu diambil? Contohnya Sampel dari webcam ini di puncak gunung: Jelas matahari bersinar. Dalam sampel lain ini, itu jauh kurang jelas: Orang mungkin dapat mendeteksi dengan mudah apakah...