196-algoritma

Pelajaran 20 dari 20 dalam kursus Teka-teki Matematika di Coddy.

Jika kita membalik 38 lalu menjumlahkannya, 38 + 83 = 121, yang merupakan bilangan palindrom.

Tidak semua bilangan menghasilkan bilangan palindrom dengan cepat. Contohnya,

37 + 73 = 110
110 + 11 = 121

Artinya, 37 memerlukan dua iterasi untuk mencapai bilangan palindrom.

Contoh lainnya, mulai dari 249:

249+942=1191
1191+1911=3102
3102+2013=5115.

Bilangan palindrom seperti 11 dan 343 dianggap menjadi bilangan palindrom dalam nol iterasi.

Ambil bilangan bulat positif apa pun, balik digit-digitnya, lalu tambahkan hasilnya ke bilangan semula. Ini adalah operasi proses balik-dan-jumlah. Ulangi prosedur tersebut dengan jumlah yang diperoleh hingga menghasilkan bilangan palindrom. Prosedur ini dengan cepat menghasilkan bilangan palindrom untuk sebagian besar bilangan bulat.

Bilangan yang tidak pernah membentuk bilangan palindrom melalui proses balik dan jumlah disebut bilangan Lychrel. Beberapa bilangan pertama yang belum diketahui dapat menghasilkan bilangan palindrom, yaitu bilangan "kandidat Lychrel", adalah 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Tantangan

Sedang

Meskipun belum ada yang membuktikannya, beberapa bilangan dalam sistem bilangan basis 10, seperti 196, tidak pernah menghasilkan palindrom. Untuk tantangan ini, kita akan menganggap suatu bilangan sebagai bilangan Lychrel sampai terbukti sebaliknya. Setiap bilangan di bawah sepuluh ribu akan (i) menjadi palindrom dalam kurang dari lima puluh iterasi, atau (ii) belum berhasil diubah menjadi palindrom oleh siapa pun, dengan seluruh daya komputasi yang ada.

Tulis fungsi isLychrel yang menerima bilangan bulat positif yang lebih kecil dari 10000, lalu mengembalikan jumlah iterasi yang diperlukan untuk menjadi palindrom.

Kembalikan -1 jika lebih dari lima puluh iterasi telah berlalu.

Coba sendiri

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = isLychrel(n);
    printf("%d\n", r);
    return 0;
}