Avtor: Matija Lokar
kot primer rešitve seminarske naloge pri predmetu Programski jeziki
Števila, ki jih lahko razstavimo na prafaktorje 2, 3, 5 ali 7 imenujemo ponižna števila. Poišči n-to ponižno število.
Vol IV: naloga 443
Pri samem algoritmu uporabimo "grobo silo". Po vrsti preverjamo za števila 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... če so ponižna. To storimo tako, da ga delimo z 2, dokler "gre" (dokler je deljivo), potem s 3, 5 in 7. Če na koncu dobimo 1, je število ponižno. Če število je ponižno, povečamo števec ponižnih števil. Ko pridemo do n-tega, se ustavimo in števec vrnemo kot rezultat. Posebej je potrebno paziti na n = 1.
Posebej sestavimo metodo, ki bo vrnila ustrezno končnico. Pazimo na 11, 12, 13, ko je končnica th, drugače pa o končnici odloča zadnja števka. Seveda se vse skupaj ponovi na vsakih 100 števil, zato kar takoj vzamemo ostanek pri deljenju s 100.
Števila, katerih edini prafaktorji so 2, 3, 5 ali 7 imenujemo ponižna števila. Zaporedje 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... predstavlja prvih 20 ponižnih števil. Napišite program, ki najde in izpiše n-ti člen tega zaporedja.
Vhodni podatek predstavlja en ali več testnih primerov. Vsak testni primer je sestavljen iz vrstice, ki vsebuje le celo število n, kjer velja 1 <= n <= 5842. Konec vhodnih podatkov označjue vrednost nič (0) za n.
Za vsak testni primer izpiši vrstico "The nth humble number is number.". Glede na n je potrebno dodati ustrezno pripono "st ", "nd ", "rd", oziroma "th" za vrstilni števnik n-ja, kot je to prikazano v primeru izhodnih podatkov.
The 1st humble number is 1.
The 2nd humble number is 2.
The 3rd humble number is 3.
The 4th humble number is 4.
The 11th humble number is 12.
The 12th humble number is 14.
The 13th humble number is 15.
The 21st humble number is 28.
The 22nd humble number is 30.
The 23rd humble number is 32.
The 100th humble number is 450.
The 1000th humble number is 385875.
The 5842nd humble number is 2000000000.
| Ponizno.java |
// Program izpiše n-ta ponižna števila
// to so števila, ki so sestavljena iz prafaktorjev 2,3,5 ali 7.
import java.io.*;
import java.util.*;
public class Ponizno {
final static int maxI = 5842; // do kje znamo izpisovati ponižna števila
public static void main (String[] mmm) throws Exception {
BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));
while(true) { // Neskoncna zanka, ustavili jo bomo z ukazom break
int nn = Integer.parseInt(vhod.readLine().trim()); // Preberemo podatek
if (nn == 0) break; // Podatek 0 pomeni konec podatkov, ustavimo zanko
if ((1 <= nn) && (nn <= maxI)) {
System.out.println("The " + nn + koncnica(nn) + " humble number is " +
humble_number(nn) + ".");
}
else {
System.out.println("Število "+ nn +" ni iz intervala [1, "+maxI+"].");
}
}
} // main
// Metoda vrne končnico vrstilnega števnika.
public static String koncnica(int nn) {
nn = nn % 100; // zanimivi sta le zadnji dve števki
if ((nn >= 11) && (nn <= 13)) return "th"; // 11, 12, 13 so posebej
nn = nn % 10; // sedaj odloca le še zadnja števka
if (nn == 1) return "st";
if (nn == 2) return "nd";
if (nn == 3) return "rd";
return "th";
} // koncnica
// Metoda vrne n-to ponižno število.
public static int humble_number(int nn) {
if (nn == 1) return 1;
int humble = 0;
int kandidat = 2;
int kateroPon = 1;
while (kateroPon < nn) { // nismo še nasli n-tega
int n_st = kandidat;
while ( n_st % 2 == 0) n_st = n_st / 2; // dokler obstaja faktor 2
while ( n_st % 3 == 0) n_st = n_st / 3; // faktor 3
while ( n_st % 5 == 0) n_st = n_st / 5; // faktor 5
while ( n_st % 7 == 0) n_st = n_st / 7; // faktor 7
if ( n_st == 1) { // ni drugh faktorjev razen 2, 3, 5, 7
humble = kandidat; // zato je število ponižno
kateroPon++;
}
kandidat++;
}
return humble;
} // humble_number
} // class
|
Poleg v nalogi navedenih primerov je zaradi končnic smiselno preveriti še npr. 101, 102, 103, 104, 111, 112, 113, 512, 634, 1011, 2212, 3333.
Primer
101 The 101st humble number is 480. 102 The 102nd humble number is 486. 103 The 103rd humble number is 490. 104 The 104th humble number is 500. 111 The 111th humble number is 576. 112 The 112th humble number is 588. 113 The 113th humble number is 600. 512 The 512th humble number is 35840. 634 The 634th humble number is 72900. 1011 The 1011th humble number is 400000. 2212 The 2212th humble number is 11337408. 3333 The 3333rd humble number is 86400000.
Naloge nisem oddal v avtomatsko preverjanje, ker ne zaupam Špancem, da bi napisali dovolj kvaliteten program, ki bi preveril moj umotvor. Sicer pa se že iz same kode vidi, da stvar zagotovo deluje. Zakaj bi stvar potem še pošiljal nekomu v preverjanje, saj sem poskusil in dela prav za 1, 2, 3, 4, 5 in 7. Ni vrag, da potem ne dela prav za vse. Sicer za 6 ne dela prav, ampak verjetno je bila to napaka računalnika (kakšen sončni izbruh v tistem trenutku je malo zmešal bite), saj je za 7 spet prav.
Programa v tem primeru nisem dal v avtomatsko preverjanje tudi zato, da lahko na posebni strani opišemo, kako bi to naredili.
[Program, ki je prestal avtomatsko preverjanje, je tule].
Prepis potrditvenega sporočila:
Your JAVA program has solved Ok the problem 443 (Humble Numbers) in 1.180 seconds using as much as 2680 kbytes of virtual memory. Congratulations! -- The Online Judge (Linux acm.uva.es 2.4.18-27.7.x i686) Judge software version 2.8 [http://acm.uva.es/problemset/] Thu Apr 15 06:29:56 UTC 2004
Opomba: Seveda vam razlaga, kot je navedena v prvem odstavku tega razdelka ne bo pomagala kaj dosti, če boste želeli prejeti oceno, višjo kot 7. Skratka - naloge naj bi bile sprejete s strani avtomatskega sodnika!
Časovna kompleksnost testiranja ponižnosti za eno število je linearna. Da poiščemo n-to ponižno število, potrbujemo n testov ponižnosti, kar pomeni, da je časovna kompleksnost našega postopka O(n2). Pri velikih n to ne bo najbolje.
Verjetno bi bilo mogoče nalogo rešiti tudi tako, da bi neposredno skonstruirali n-to ponižno število. Če formule ne znamo ugotoviti, bi si lahko pomagali tudi s pomočjo slovarja, kjer bi sistematično zgenerirali ponižna števila kot četverke (a, b, c, d), kjer bi a pomenilo število faktorjev 2 (potenco pri 2), b število faktorjev 3, ... in jih hranili urejeno glede na generirano število (produkt 2a*3b*5c*7d). Potem bi za vsak testni primer le vrnili ustrezen element.
Števila, katerih edini prafaktorji so 2, 3, 5 ali 7 imenujemo ponižna števila. Zaporedje 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... predstavlja prvih 20 ponižnih števil. Napišite program, ki izpiše prvih n ponižnih števil.
Števila, ki ne vsebujejo prafaktorjev 2, 3, 5 ali 7 imenujemo neponižna števila. Zaporedje 1, 11, 13, 17, 19, 29, 31, 37, 41 predstavlja prvih 9 neponižnih števil. Napišite program, ki izpiše n-to neponižno število.