5-mavzu: Algoritmik yechilmaydigan muammolar. Mayxil teoremasi. Algoritmik darjalar

Musbat butun sonni olganingizda, raqamlarni almashtiring va olingan raqamni asl raqamga qo'shing. Palindrom paydo bo'lgunga qadar jarayonni necha marta takrorlash kerak? Palindrom - chapdan o'ngga va o'ngdan chapga o'qilganda raqamlari bir xil bo'lgan raqam. LINK - dastur mavjud Masalan, 5280 uchun biz 3 qadamdan keyin palindrom olamiz (har bir qadam satrni teskari qiladi va ikkalasini ham qo'shadi) 1-qadam: 5280+0825=6105 2-qadam: 6105+5016=11121 3-qadam: 11121+12111=23232

Agar tasvirlangan qadamni qayta-qayta bajara boshlasak va palindrom hosil qilsak, algoritm tugaydi. Biroq, 100 qadam, 1000 qadam, 10 000 qadamdan keyin palindromga ega bo'lmasak, qanday xulosa chiqarishimiz mumkin? Biz to'xtab, "10 000 takrorlashdan keyin palindrom yaratmadik" deyishimiz mumkin, ammo palindromni keyinroq topib bo'lmaydi, deb ayta qila olmaymiz. Haqiqatan ham, " hech qanday palindrom yaratib bo'lmaydi" degan javobni yaratadigan algoritm yo'q.”

Quyida "aylantirish va palindromga qo'shish" vazifasi uchun kod mavjud. Kod while tsiklini o'z ichiga oladi while (no is_palindrome(raqam) va qadam

palindrom topilganda yoki vaqt tugaganda tugaydi! Kirish sifatida 196 bilan kodni ishga tushiring. Hali hech kim palindrom topmagan. Dasturni our_limit=10000 bilan ishga tushirish uni topa olmaydi. Agar dasturni belgilangan cheklovsiz ishga tushirsangiz, cheksiz tsikl paydo bo'ladi.

Agar biz qadam < bizning_chegaraviy shartni olib tashlasak, bizda algoritm tugamasligi mumkin bo'ladi. Ko'pgina tamsayılar uchun u aslida tugaydi. Biroq, 196 uchun biz bu oddiy algoritm tugatiladimi yoki yo'qligini bilmaymiz. To'xtamasligini hech kim isbotlay olmadi.

import math
# teskari raqamni oling
def reverse_num(n):
num = str(n)
rev_num = "" # bekor qilingan raqamni bo'sh deb boshlang
x = len(num) - 1 # kirish raqamining uzunligini toping
for i in range(x, -1, -1): # num oxiridan boshlang va orqaga harakatlaning
digit = num[i] # raqamni oling
rev_num = rev_num + digit # uni rev_num oxiriga qo'shish
return rev_num