Algoritma Backtracking : "Habis Dibagi". Angka-angka 1,2,3,4,5,6,7,8,9 dapat disusun dalam suatu urutan tertentu. Kesembilan angka harus dipergunakan semua dengan kata lain tidak boleh dipakai lebih dari satu kali, sehingga :

1. Untuk mengatasi masalah ini tulislah terlebih dahulu sebuah fungsi boolean (outputnya hanya true atau false): FUNCTION habis(bil[], jumlevel). Fungsi ini akan memeriksa apakah susunan digit sebanyak jumlevel yang tersimpan dalam vektor bil[] memenuhi syarat, artinya untuk semua nilai i=2,3,4,.....jumlevel, apakah bilangan yang terbentuk oleh i angka pertama habis dibagi oleh i ? Contoh:

• Jika bil[] berisi 1, 2, 6 dan leveldigit=3 ; maka output fungsi ini true karena 12 mod 2 = 0, dan 126 mod 3 = 0.

• Jika bil[ ] berisi 2, 4, 3, 6, 5 dan leveldigit=5 ; maka output fungsi ini juga true karena 24 mod 2, 243 mod 3, 2436 mod 4; dan 24365 mod 5 semuanya menghasilkan angka 0 (habis dibagi).

• Jika bil[ ] berisi 2, 4, 3, 8 dan leveldigit=4 ; maka output fungsi ini false karena walaupun 24 mod 2=0; 243 mod 3=0; tetapi 2438 mod 4 <> 0.

Bantuan untuk mempermudah pekerjaan Anda: Abstraksi dan algoritma detil yang dibuat harus menggunakan vektor bil[] sebanyak 9 elemen untuk menampung hasilnya. Sebagai contoh bila algoritma ini akan menghasilkan bilangan 381654729, maka vektor bil[] akan berisi 3,8,1,6,5,4,7,2,9. Selain itu gunakan pula FUNCTION habis(bil[], jumlevel).

3. Dari abstraksi yang telah dibuat, kembangkan untuk menulis algoritma (detil) backtrackingnya, dengan nama PROCEDURE cobadigit(ke), dimana ke adalah levelnya, mulai dari 1 sampai 9.

4. Tulis pula  algoritma (lengkap) utama pemanggilnya, lengkap dengan inisialisasi vektor bil[] dan pencetakan hasilnya.

Subgoal yang Recursive: "The Dashes and Stars Banner". Bendera negara UNITED STATES OF AlphanuMERICA tersusun dari sejumlah karakter dashes (-) dan stars (*) yang disusun silih berganti dalam beberapa baris seperti tampilan berikut ini, sehingga bendera ini sering disebut "The Dashes and Stars Banner":

----------------****************   k dashes diikuti k stars

--------********--------********   k/2 dashes diikuti k/2 stars

----****----****----****----****   ... demikian seterusnya

--**--**--**--**--**--**--**--**   ... digandakan dan dibagi 2

-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*   sampai panjangnya 1.

Berbasis konsep subgoal, tulis recursive procedure DrawFlag(k), yang akan mencetak bendera negara tersebut mulai dengan k-dashes dan k-stars. Diasumsikan nilai k selalu 2n untuk n=0,1,2,..... Validitas k tidak perlu diperiksa lagi.

Recursive: "Fungsi Satu Baris Saja....." Perhatikan subalgoritma function satu baris di bawah ini:

 

FUNCTION max3 ( a, b, c)

1. max3 <----- max(a, max(b, c))

2. RETURN

1. Tulislah subalgoritma function max, sehingga FUNCTION max3 dapat dipakai untuk mendapatkan nilai maksimal dari 3 buah bilangan integer a, b, dan c? Sebagai contoh max(12, 17, 9) akan menghasilkan 17; sedangkan max(14, 16, 18) akan menghasilkan 18.

2. Dengan memanfaatkan jawaban nomor (a). tulislah subalgoritma fungsi untuk mendapatkan nilai maksimal dari 5 buah bilangan integer, dengan nama max5. Sebagai contoh max5(2, 17, 29, 18, 26) akan menghasilkan 29; sedangkan max5(74, 71, 50, 76, 88) akan menghasilkan 88.

State-Space Search : "Batu Hitam dan Batu Putih". Terdapat sebuah kotak kayu dengan 5 (lima) lubang. Sebuah lubang hanya dapat terdiri dari sebuah batu atau kosong. Pada keadaan awal, 2 batu hitam diletakkan di lubang ujung kiri kotak, sedangkan 2 batu putih diletakkan di lubang ujung kanan kotak. Sementara sebuah lubang yang tepat di tengah kotak dibiarkan kosong. 

Posisi batu hitam dan batu putih ingin ditukar, sehingga 2 batu hitam diletakkan di lubang ujung kanan kotak, sedangkan 2 batu putih diletakkan di lubang ujung kiri kotak.

1. Tulis sub-algoritma procedure Recursive_Fibonacci_Search.

2. Terdapat sebuah vektor A[ ] yang telah tersorting secara ascending order sejumlah 14 elemen integer : 04 29 29 34 47 55 55 55 67 76 76 76 98 98. Tunjukan perbandingan-perbandingan yang dilakukan, termasuk perubahan alokasi range pencarian data (perubahan variabel LOW dan HIGH) saat mencari data x = 55 pada vektor A[] dengan menggunakan Recursive Fibonacci Search.

Ulangi algoritma pada soal nomor (6) di atas, juga dengan divide and conquer, hanya tidak diketahui bahwa berat coin yang palsu apakah lebih ringan atau lebih berat? Prinsipnya berat yang palsu berbeda dengan semua lainnya yang asli.

10.

Write an algorithm to count the number of times a given target value occurs in an array of N integers recursively.

2 1 5 1                   2 1 5 1