Wisatawan, halo.
Jika Anda membaca ini, saya menyarankan kelanjutan dari materi "menghibur" yang saya tulis sebelumnya. Jika Anda mengikuti sedikit pemikiran, yang bercabang menjadi tiga artikel, tetapi pesan utamanya adalah - hanya untuk menunjukkan minat pada pendekatan deklaratif. Untuk beberapa alasan, ini tidak bagus, seolah-olah eSCuel tidak menjadi tersedia untuk umum dan wajib, karena tanpa eSCuel tidak mungkin untuk memikirkan bagaimana data dapat diproses secara berbeda. Benar, lebih baik merumuskan tugas dan tidak khawatir tentang apa artinya ini.
Mari kita turun ke bisnis, saya menulis sebelumnya tentang mencoba menghibur Anda, jadi saya akan terus menunjukkan contoh menggunakan prolog, meskipun artikel sebelumnya telah menunjukkan bahwa minat pada python dan bahkan pergi akan membangkitkan minat segera untuk beberapa ribu orang, yang tertarik pada berita tentang baterai baru Tesla, adalah pandangan stotysch, dan untuk menulis program pada razrabotnichestskom Portal tidak begitu sedikit, terlihat di balik perilaku ini dicatat pada membaca komentar, dan mungkin lIMA dari mereka, setelah pembacaan kedua usulan esch ini Ini membingungkan gagasan bahwa hal itu harus membaca lebih ...
Ternyata hipotesis yang menarik tidak terpenuhi, dan kemudian saya hanya menunjukkan bagaimana menggunakan prolog, itu adalah alat yang modern, berkembang, dan didistribusikan secara bebas, dapat diambil dan dirumuskan, hanya agar dapat dirumuskan untuk melihat keuntungan.
Saya akan mengatakan bahwa perjalanan waktu tidak ada, tetapi kita akan pergi seminggu yang lalu, ada Prolog yang menarik tentang tiga bagian dalam rekaman itu, di situlah topik penyelesaian masalah baru yang secara acak tersentuh tersentuh, saya mengambil situs yang menarik ini , dan tugas yang paling sulit (hanya tidak mengubah string menjadi angka)), saya akan mencoba melakukannya di Prolog .
Berhentilah meningkatkan minat, mulai ...
Urutan angka disebut aritmatika jika terdiri dari setidaknya tiga elemen dan jika perbedaan antara dua elemen berturut-turut adalah sama.
Sebagai contoh, ini adalah urutan aritmatika:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
Urutan berikut ini bukan aritmatika.
1, 1, 2, 5, 7
Semua dalam semua, perbedaan antara kedua tetangga harus dilestarikan, hanya perlu memeriksa ini?
Baca terus:
Array nol-diindeks A yang terdiri dari angka N diberikan. Sepotong berikutnya dari array itu adalah setiap urutan bilangan bulat (P0, P1, ..., Pk) sedemikian sehingga 0 ≤ P0 <P1 <... <Pk <N.
Irisan berikutnya (P0, P1, ..., Pk) dari array A disebut aritmatika jika urutan A [P0], A [P1], ..., A [Pk-1], A [Pk] adalah aritmatika . Secara khusus, ini berarti bahwa k ≥ 2.
Fungsi harus mengembalikan jumlah irisan urutan aritmatika dalam array A.
Wow, kata-kata, Anda perlu mencari tahu berapa banyak irisan yang dapat Anda temui, berapa banyak opsi untuk sublist yang dapat Anda temukan, sehingga perbedaan antara item yang berdekatan tidak berbeda.
Seolah-olah sublist berada dalam satu set besar semua permutasi dari daftar input.
Contoh:
Input: [2, 4, 6, 8, 10]
Output: 7
Penjelasan:
Semua irisan aritmatika selanjutnya adalah:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
Saya tahu cara mengekspresikan sublist di prolog, ini:
sublists(InputList, SubList):- append(Prefix,Root,InputList), append(SubList,Suffix,Root).
Cara memeriksa bahwa daftar jenis yang diinginkan diperlukan untuk check in tiga kali lipat:
is_seq(A,B,C]):-AB =:=BC. is_seq(A,B,C|Tail]):-AB =:=BC, is_seq(B,C|Tail]).
Jika kita membuang permutasi dari semua elemen daftar, ternyata ini bukan hanya sublist dari elemen yang berdiri di dekatnya, itu adalah sublist yang dibentuk dengan melewatkan item.
Lalu letakkan seperti ini:
seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1).
Aturan seperti itu akan mengembalikan semua kemungkinan daftar dari daftar, tetapi bisa mulai dari satu elemen, atau melewatkannya, dari yang berikutnya, juga jumlah apa pun dapat dibuang di akhir.
Secara total, kami mendapatkan jumlah solusi yang terlalu tinggi, segera jelas bahwa daftar kosong akan kembali berkali-kali, dan pengulangan tidak dapat dihindari ketika elemen dijatuhkan dari ujung.
Setelah meninjau tes yang diusulkan untuk masalah ini, ternyata mungkin ada nilai duplikat pada input, bahwa untuk daftar seperti itu [0,1,2,2,2] harus ada 4 solusi. Setiap 2-ka dapat diambil secara terpisah, dan ini harus dianggap sebagai irisan terpisah, sehingga tiga opsi [0,1,2] dan satu [2,2,2] cocok.
Ini nasib buruk, karena generator urutan akan menghasilkan nilai duplikat, tetapi bagaimana membuat perhitungan hanya unik? Anda harus menandai mereka, membuat daftar berbeda satu sama lain. Saya akan membangun seluruh solusi berdasarkan pembuatan daftar, memeriksa kondisi dan menghitung jumlah solusi. Dan apa yang harus dilakukan dengan pengulangan keputusan ...
Saya akan membuat penomoran elemen secara sederhana, biarkan daftar berubah menjadi daftar komponen Nilai / Indeks, istilah terstruktur, begitulah mereka menyebutnya. Untuk contoh di atas, ini akan menjadi [0 / 1,1 / 2,2 / 3,2 / 4,2 / 5]. Urutan yang dihasilkan oleh input ini semua akan berbeda.
Jadi, Anda dapat mengubah daftar menjadi yang ditandai:
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1).
Nah dan poin paling penting, memeriksa aritmatika is_seq, setelah serangkaian upaya, dengan mempertimbangkan daftar yang ditandai, aturan ini berubah menjadi ekspresi yang agak rumit. Di sini kami memeriksa bahwa tiga kali lipat angka sesuai dengan kondisi, dan menghitung kunci dari solusi khusus ini, untuk mengecualikan solusi unik, diperlukan kunci, ini akan membantu untuk mengumpulkan semua kunci dalam daftar dan kemudian menghitungnya.
Pada input adalah daftar yang ditandai, output akan menjadi nilai kunci, menghitungnya sebagai bilangan bulat yang digitnya adalah jumlah dari Nilai + Indeks untuk setiap elemen.
%is_seq , , is_seq([A/An,B/Bn,C/Cn],2,N):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, is_seq([B/Bn,C/Cn|T],K1,N1), K is K1+1, N is N1+(A+An)*(100**K).
Untuk menghitung semua solusi, saya akan menggunakan kemampuan bawaan untuk memenuhi tujuan dan mengumpulkan semua solusi unik ke dalam daftar setof (). Cukup dengan menyusun daftar semua urutan ternyata sama sekali tidak efektif, dari sinilah muncul ide kunci sebagai nilai yang lebih sederhana:
get_number(List,N) :- label(List,ListL,1), setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result), length(Result,N),!. get_number(_,0).
Tentu saja, kinerja tidak secara khusus dinyatakan dalam solusi semacam itu.
Berikut ini adalah teks program yang lengkap, dengan daftar tes, yang diambil dari situs dengan tugas (ini hanya bagian dari tes):
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1). seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1). is_seq([A/An,B/Bn,C/Cn],2,N):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, is_seq([B/Bn,C/Cn|T],K1,N1), K is K1+1, N is N1+(A+An)*(100**K). get_number(List,N) :- label(List,ListL,1),setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result), length(Result,N),!. get_number(_,0). %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %all test :-assert_are_equal(get_number([2,4,6,8,10],7),true). :-assert_are_equal(get_number([],0),true). :-assert_are_equal(get_number([1],0),true). :-assert_are_equal(get_number([1,2],0),true). :-assert_are_equal(get_number([1,2,3],1),true). :-assert_are_equal(get_number([1,2,3,4],3),true). :-assert_are_equal(get_number([1,2,3,4,5],7),true). :-assert_are_equal(get_number([1,2,3,4,5,6],12),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7],20),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8],29),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9],41),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9,10],55),true). :-assert_are_equal(get_number([2,2,3,4],2),true). :-assert_are_equal(get_number([0,1,2,2,2],4),true). :-assert_are_equal(get_number([0,2000000000,-294967296],0),true). :-assert_are_equal(get_number([1,1,1],1),true). :-assert_are_equal(get_number([1,1,1,1],5),true). :-assert_are_equal(get_number([1,1,1,1,1],16),true). :-assert_are_equal(get_number([1,1,1,1,1,1],42),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1],99),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1],219),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1],466),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1],968),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1],1981),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1],4017),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1],8100),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1],16278),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],32647),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],65399),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],130918),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],261972),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],524097),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],1048365),true).
Sebagai hasil yang mengecewakan, berikut ini efisiensinya:
get_number([2, 4, 6, 8, 10], 7)->ok:0/sec get_number([], 0)->ok:0/sec get_number([1], 0)->ok:0/sec get_number([1, 2], 0)->ok:0/sec get_number([1, 2, 3], 1)->ok:0/sec get_number([1, 2, 3, 4], 3)->ok:0/sec get_number([1, 2, 3, 4, 5], 7)->ok:0/sec get_number([1, 2, 3, 4, 5, 6], 12)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7], 20)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8], 29)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8, 9], 41)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 55)->ok:0/sec get_number([2, 2, 3, 4], 2)->ok:0/sec get_number([0, 1, 2, 2, 2], 4)->ok:0/sec get_number([0, 2000000000, -294967296], 0)->ok:0/sec get_number([1, 1, 1], 1)->ok:0/sec get_number([1, 1, 1, 1], 5)->ok:0/sec get_number([1, 1, 1, 1, 1], 16)->ok:0/sec get_number([1, 1, 1, 1, 1, 1], 42)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1], 99)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1], 219)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1], 466)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 968)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1981)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 4017)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 8100)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 16278)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 32647)->ok:1/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 65399)->ok:1/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 130918)->ok:3/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 261972)->ok:6/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 524097)->ok:12/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1048365)->ok:27/sec
Mengumpulkan daftar, bahkan hanya kunci keputusan, sangat rumit, tetapi ini adalah keputusan deklaratif, yang tanpanya tidak mungkin untuk menghitung semua solusi unik.
Kesimpulan
Ini adalah bagaimana tugas-tugas dalam bahasa Prolog dirumuskan, hanya mentransfer pernyataan masalah ke program penuh dengan efisiensi yang tidak mencukupi. Atau mungkin dalam masalah ini hanya solusi algoritmik yang tersedia? Seberapa rumit prosesnya?
Sekali lagi saya meninggalkan pertanyaan ...
Meski begitu, pencarian jawaban menarik dalam profesi kita, bukan?