Tulis fungsi / subrutin untuk mengurutkan daftar bilangan bulat, gaya Tower of Hanoi .
Anda akan diberi setumpuk bilangan bulat. Ini tumpukan utama.
Anda juga diberi dua tumpukan helper. Tumpukan pembantu ini memiliki properti unik: setiap elemen harus lebih kecil dari atau ukuran yang sama dengan elemen di bawahnya. Stack utama tidak memiliki batasan seperti itu.
Anda ditugaskan menyortir tumpukan utama, meletakkan bilangan bulat terbesar di bawahnya. Fungsi / subrutin Anda akan mengembalikan (atau setara) jumlah gerakan yang dibuatnya dalam menyortir tumpukan.
Catatan: Anda harus mengurutkan tumpukan utama di tempat , tidak mengurutkan ke tumpukan lain dan menyebut itu jawabannya. Namun, jika Anda karena suatu alasan tidak dapat melakukannya, Anda dapat mensimulasikan tumpukan yang bisa berubah, tetapi ingat bahwa ini adalah semacam Menara Hanoi; hanya ada 3 pasak dan hanya 1 pasak yang dapat diurangkan.
Fungsi / subrutin Anda dapat memeriksa tumpukan apa saja kapan saja, tetapi hanya dapat bergerak dengan membuka dan mendorong. Satu gerakan adalah pop dari satu tumpukan yang didorong ke yang lain.
Uji fungsi / subrutin Anda untuk setiap permutasi dari 6 bilangan alami pertama. Dengan kata lain, uji fungsi / subrutin Anda untuk {1},{2},...,{6},{1,1},{1,2},...,{1,6},{2,1},...
(ini harus total atau kemungkinan (terima kasih kepada Howard untuk mengoreksi matematika saya)). Fungsi / subrutin yang menggerakkan elemen paling sedikit menang.61+62+...+66
55986
sumber
6**1+6**2+...+6**6=55986
elemen.Jawaban:
Java - solusi optimal (1080544 bergerak)
Solusi ini membangun pohon jalur terpendek dari target dan mundur, kemudian melintasi jalur dari keadaan awal ke target. Banyak ruang untuk peningkatan kecepatan, tetapi masih menyelesaikan semua masalah 5.9986 dalam waktu sekitar satu menit.
Dengan asumsi algoritma diimplementasikan dengan benar, ini harus menjadi solusi terbaik secara teoritis.
sumber
C - 2547172 untuk 55986 input
Ada banyak ruang untuk perbaikan di sini. Untuk kewarasan saya sendiri, saya menyederhanakan ini sehingga hanya mungkin untuk memeriksa elemen teratas dari setiap tumpukan. Mengangkat pembatasan yang diberlakukan sendiri ini akan memungkinkan optimisasi seperti menentukan urutan akhir sebelumnya dan mencoba meminimalkan jumlah gerakan yang diperlukan untuk mencapainya. Contoh yang menarik adalah bahwa implementasi saya memiliki perilaku kasus terburuk jika tumpukan utama sudah diurutkan.
Algoritma:
Analisis:
sumber
Python,
39838383912258 bergerak lebih dari 55.986 inputIni sangat tidak efisien.
Saya akan menambahkan jumlah total pergerakan setelah OP mengklarifikasi apakah itu untuk semua kasus atau untuk kasus spesifik lainnya.
Penjelasan
Apa, komentar tidak cukup baik untuk Anda?
Catatan untuk OP: Terima kasih karena tidak membuat golf kode ini.
sumber
[2,1,1]
apakah ada cara untuk mendapatkan[2,1,1].index(1)
2 yaitu mulai dari yang lebih tinggi?[2,1,1,3,5].index(1)==2
alih-alih1
list.index(data)
mengembalikan indeks itemdata
dalamlist
. Saya tidak tahu indeksdata
yaitu1
len(list)-(list[::-1].index(1))
Python:
1.688.2931.579.1821.524.0541.450.8421.093.195 bergerakMetode utamanya adalah
main_to_help_best
memindahkan beberapa elemen yang dipilih dari tumpukan utama ke tumpukan pembantu. Ini memiliki benderaeverything
yang menentukan apakah kita ingin memindahkan semuanya ke yang ditentukandestination
, atau apakah kita ingin menyimpan hanya yang terbesardestination
sementara sisanya di pembantu lainnya.Andaikan kita pindah ke
dst
menggunakan helperhelper
, fungsinya secara kasar dapat digambarkan sebagai berikut:helper
rekursifdst
helper
ke utamadst
everything
diatur, pindahkan elemen secara utama ke utamadst
b. Jika tidak, pindahkan elemen secara utama ke
helper
Algoritme pengurutan utama (
sort2
dalam kode saya) kemudian akan memanggilmain_to_help_best
denganeverything
set keFalse
, dan kemudian memindahkan elemen terbesar kembali ke utama, kemudian memindahkan semuanya dari helper kembali ke utama, menjaganya agar tetap diurutkan.Penjelasan lebih lanjut tertanam sebagai komentar dalam kode.
Pada dasarnya prinsip yang saya gunakan adalah:
Prinsip 3 diterapkan dengan tidak menghitung langkah jika sumbernya adalah tujuan sebelumnya (yaitu, kami baru saja memindahkan utama ke bantuan1, maka kami ingin pindah dari bantuan1 ke bantuan2), dan selanjutnya, kami mengurangi jumlah gerakan sebesar 1 jika kami memindahkannya kembali ke posisi semula (mis. main to help1 lalu help1 ke main). Juga, jika
n
gerakan sebelumnya semuanya menggerakkan bilangan bulat yang sama, kita sebenarnya dapat menyusun ulangn
gerakan tersebut. Jadi kami juga memanfaatkan itu untuk mengurangi jumlah gerakan lebih jauh.Ini valid karena kita tahu semua elemen di tumpukan utama, jadi ini bisa diartikan sebagai melihat di masa depan bahwa kita akan memindahkan elemen kembali, kita tidak boleh melakukan langkah ini.
Contoh dijalankan (tumpukan ditampilkan dari bawah ke atas - jadi elemen pertama adalah bawah):
Kita dapat melihat bahwa kasus terburuk adalah ketika elemen terbesar ditempatkan di bagian bawah kedua, sedangkan sisanya diurutkan. Dari kasus terburuk kita dapat melihat bahwa algoritma ini adalah O (n ^ 2).
Jumlah gerakan jelas minimum untuk
n=1
dann=2
seperti yang dapat kita lihat dari hasilnya, dan saya percaya ini juga minimum untuk nilai yang lebih besarn
, meskipun saya tidak dapat membuktikannya.Penjelasan lebih lanjut ada dalam kode.
sumber
4
. Apa ini menyimpan elemen terbesar kedua pada helper kedua? Apa artinya?Java -
21290902083142 bergerak di 55986 arrayThe ideone Link .
Kerangka kerja untuk memastikan algoritma tersebut benar:
Algoritma yang sebenarnya:
Testcase:
sumber
C / C ++ Tidak mengukur gerakan (pasak: p1, p2, p3) Tidak tahu cara menambahkan kode C ++ yang menggunakan STL (masalah formating). Kehilangan bagian kode karena format tag html dalam kode.
Gabungkan pindahkan (n + m) data dalam p2 & p3 ke p1.
sumber
hanoi(...)
fungsinya. Juga, Anda memiliki 2#include
s yang tidak dikompilasi. Silakan kirim kode lengkap.