Rumah > Artikel > pembangunan bahagian belakang > Bagaimana untuk melaksanakan algoritma tamak menggunakan Python?
Bagaimana untuk melaksanakan algoritma tamak menggunakan Python?
Algoritma Greedy ialah algoritma yang mudah dan berkesan sesuai untuk menyelesaikan masalah dengan sifat substruktur yang optimum. Ia memerlukan pilihan terbaik dalam keadaan semasa dalam setiap langkah pemilihan, dengan harapan dapat mencari penyelesaian optimum global. Dalam artikel ini, kami akan memperkenalkan cara menggunakan Python untuk melaksanakan algoritma tamak, dengan contoh kod tertentu.
1. Idea asas algoritma tamak
Idea asas algoritma tamak adalah untuk memilih penyelesaian optimum dalam keadaan semasa pada setiap langkah, dan kemudian meneruskan ke langkah seterusnya. Algoritma tamak bukan algoritma yang boleh menyelesaikan semua masalah, tetapi sesuai untuk beberapa masalah dengan sifat pemilihan tamak. Masalah ini mempunyai dua ciri berikut:
Berdasarkan dua ciri ini, apabila menggunakan algoritma tamak, anda perlu memberi perhatian sama ada masalah itu memenuhi sifat substruktur yang optimum dan secara munasabah memilih penyelesaian optimum untuk setiap langkah.
2. Langkah-langkah pelaksanaan algoritma tamak
Langkah pelaksanaan algoritma tamak biasanya termasuk langkah-langkah berikut:
3. Contoh penggunaan Python untuk melaksanakan algoritma tamak
Berikut mengambil masalah perubahan sebagai contoh untuk menunjukkan cara menggunakan Python untuk melaksanakan algoritma tamak.
Soalan: Katakan terdapat wang kertas 1 yuan, 2 yuan, 5 yuan, 10 yuan, 20 yuan, 50 yuan dan 100 yuan, dan bilangan perubahan yang diperlukan untuk memberi pelanggan ialah n yuan, cara menggunakan minimum bilangan wang kertas untuk menukar pelanggan pelanggan?
Idea pelaksanaan:
Berikut ialah contoh kod khusus menggunakan Python untuk melaksanakan algoritma tamak untuk menyelesaikan masalah perubahan:
def make_change(n): denominations = [100, 50, 20, 10, 5, 2, 1] count = 0 for denomination in denominations: count += n // denomination n = n % denomination return count # 测试示例 print(make_change(47)) # 输出结果为4,使用1个20元、2个2元和1个1元 print(make_change(123)) # 输出结果为6,使用1个100元、1个20元和3个1元
Dalam kod di atas, fungsi make_change menerima integer n sebagai parameter, menunjukkan bilangan perubahan yang diperlukan. Pertama, tentukan senarai denominasi denominasi wang kertas, disusun mengikut tertib daripada terbesar kepada terkecil. Kemudian, gunakan gelung for untuk mengulangi setiap denominasi dan hitung bilangan nota yang diperlukan dan jumlah yang tinggal. Akhir sekali, kembalikan bilangan kiraan wang kertas.
Melalui contoh di atas, kami menunjukkan cara menggunakan Python untuk melaksanakan algoritma tamak untuk menyelesaikan masalah perubahan. Langkah-langkah pelaksanaan algoritma tamak adalah untuk menentukan sifat pemilihan tamak masalah, menguraikan masalah kepada beberapa sub-masalah, mereka bentuk algoritma tamak untuk menyelesaikan setiap sub-masalah dan menggabungkan penyelesaian optimum tempatan.
Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma tamak menggunakan Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!