№4 Masala yechimi
Yechilishi:
Avvalroq aytganimizdek, agar dasturingizda ishlatiladigan sonlar oddiy tiplarga sig’masa, unda satrlarda yoki massivlardan foydalaning. Bunnan tashqari BigInteger va BigDecimal sinflari ham bor, ular haqida keyinroq to’xtalib o’tamiz...
4-masalani yechish uchun satrlardan foydalanamiz. Ya’niy, kiritiladigan N butun sonni satr sifatida kiritamiz. Keyin bu satrli son bo’lgani uchun, uning ustida matematik amallarni to’g’ridan-to’g’ri ishlata olmaymiz. Lekin harxil sonlarni olib qarasak, qandaydir ketma-ketlikni topish mumkin.
Masalan, 25 sonini olsak, bu son bo’luvchilari: 1, 5, 25. Buning ichida eng yomoni 1 (eng yomonini aniqlash uchun masala shartini qaytadan o’qing). 16 sonini olsak, bu son bo’luvchilari: 1, 2, 4, 8, 16. Eng yomoni 1. 100 sonini olsak, bo’luvchilari: 1, 2, 4, 5, 10, 20, 25, 50, 100. Bunda eng yomoni 1 emas, balki 100. Chunki, raqamlari yig’indisi teng bo’lganida, kattasi eng yomon son xisoblanadi.
Bundan ko’rinadiki, eng yomon bo’luvchilari orasidagi talabgorlar: 1, 10, 100, 1000, … Agar bo’luvchilari orasida 1 dan keyin eng ko’p 0 bor son bo’lsa, shu son eng yomoni bo’lar ekan. Buni son bo’luvchilarini bilmastan turib ham aniqlash mumkin. Masalan, 1099280 sonining eng yomon bo’luvchisi 10 ekanligi ko’rinib turibdi. Chunki, bu son 100 ga yoki undan yuqori noli bor songa bo’linmaydi. Shunga o’xshash, 190290000 sonining eng yomon bo’luvchisi: 10000, 10000000 sonining eng yomon bo’luvchisi shu sonni o’zi, 102192873827372777 sonining eng yomon bo’luvchisi esa 1 ekanligi ko’rinib turibdi.
Demak, kiritilgan sonning faqat oxiridagi nollarini olib, oldiga 1 ni yozib javobga chiqaramiz ekan)
Algoritm:
- S satrni kiritamiz (butun uzun son);
- H = “1” satrini olamiz;
- I = S.length() - 1; - satr uzunligi ya’niy belgilari soni;
- Eger I==0 yoki S.charAt(I) != ‘0’ bo’lsa 8-qadamga o’tilsin;
- H = H + “0”;
- I = I – 1;
- 4-qadamga o'tilsin;
- Natiyjaga H chiqarilsin;
- Algoritm yakunlansin.
Dastur kodi (Javada):
Siz bunnanda yaxshiroq, samaraliroq algortim tuzsangiz bizga xabar bering!
Bog’lanish uchun: A.Orınbaev