Algoritmus amely meghatározza egy természetes szám legkisebb számjegyét. Légyszi valaki segit?

…

Legyen a szám n.

Fogjunk egy min változót, legyen min n utolsó jegye.

Most jön egy ciklus, amíg n nem 0: n-ből kivonjuk az utolsó jegyét, és elosztjuk a számrendszer alapszámával, az így kapott számmal felülírjuk n-et. Ha min nagyobb, mint n utolsó jegye, akkor min-t n utolsó jegyére cseréljük, és itt a ciklus vége.

Az legkisebb számjegy min.

Hogy hogyan kell kitalálni az n utolsó jegyét, azt rád bízom.

Ha már lusta megvalósítás, akkor itt egy C nyelven (n a természetes szám, x a keresett számjegy, b > 1 (EZ FONTOS!) a számrendszer alapszáma):

int x, n, b;

…

x=n%b;for(;n;n/=b)if(x>n%b)x=n%b; /*Eztán x a keresett érték lesz.*/

…

Ha nagyon kell, akkor még így lehet gyorsítani egy kicsit:

x=n%b;for(;x&&n;n/=b)if(x>n%b)x=n%b; /*Ugye x nem lehet kisebb 0-nál, így ha 0, akkor abbahagyhatjuk.*/

De biztos van lehet még kicsit gyorsítani meg rövidíteni is, én elég amatőr C programozó vagyok.

> „Teljesen mindegy, hogy mi az alap, ha a számjegyekről van szó.”

Ezt nem vágom… Például az n = 713 legkisebb számjegyének értéke b = 10-es alapú számrendszerben x = 1; b = 7-esben x = 0; b = 17-esben x = 2; b = 812-esben pedig x = 713.

> „A szám érvényességét lehet vizsgálni, illetve figyelni arra, hogy 9 után az "a" jön, és így tovább z-ig.”

Ezt sem vágom. Szerinted a 713-at nem lehet felírni valamelyik számrendszerben? Mi az, hogy egy adott természetes szám nem érvényes? Lényegében az első számelmélet előadáson azzal kezdtük, hogy bármely n természetes szám felírható egy b > 1 egész alapú számrendszerben.

A b > 1 azért fontos, mert egyrészt b = 1 esetén végtelen ciklusba lépünk (másrészt meg az 1-es és 0-s számrendszereknek amúgy sincs sok értelme).

És ha már írogatok, akkor megjegyzem, hogy a javasolt gyorsítás butaság. Ha nem szerepel 0 a számban, akkor egészen biztosan csak lassít.

szerintem rosszul fogjátok meg a dolgot.

teljesen tökmindegy, hogy mi a számrendszer alapja, csak bonyolítja a dolgot, mert figyelembe kell venni. valójában lényegtelen, mert a kérdéses számjegy ott van a begépelt karakterek között.

nem számként kell bekérni, hanem szövegként és egyszerűen írni kell egy cserélgetős nagyság szerint sorba rendező algoritmust az egymás után következő karakterekre legkisebbtől a legnagyobbig (kódtábla szerint). aztán, ha kész van a rendezés kidobni az első karaktert a képerőre.

a kutyát nem érdekli, hogy ez egy szám.

Mivel nem volt szó számrendszerekről, ezért közmegegyezéssel ilyenkor mindig 10-es számrendszerben dolgozunk. De mint írták előttem, maximum annak az ellenőrzésében van szerepe a számrendszernek, hogy a szám érvényes szám-e. Amennyiben külső inputból jön a szám, akkor az ellenőrzésnél ez lehet szempont – hogy mondjuk a 53 lehet-e érvényes 4-es számrendszerbeli szám, vagy sem –, de itt nem ezen van a hangsúly.

Ha tudjuk, hogy az adott szám érvényes számjegyekből áll, akkor innen lehet kezelni stringként. Nem kell elosztani a számrendszer alapjával, hiszen a 2 az 2, akár tízes, akár nyolcas, akár tizenhatos számrendszerben nézem.

A karaktertömbbé alakítás, sorba rendezés elvileg jó megoldás de nem optimális, hiszen egy rendezésnél többször végig kell menni az összes elemen.

Az sem optimális, ha veszem a számjegyeket, és ellenőrzöm, hogy tartalmazza-e a szám, hiszen mondjuk egy sok kilencesből álló szám esetén kilencszer kell végigmenni az összes számjegyen.

Az optimális az, ha veszem az első számjegyet, külön letárolom, majd *egyszer* végigmegyek az összes számjegyen, ha találok kisebb számjegyet, akkor lecserélem.

Programnyelvtől függetlenül valami ilyesmi (legyen a szám egy „szam” nevű, legalább 1 elemből álló karaktertömb):

legkisebb = szam[0]

hossz = strlen(szam)

for ( i=1 ; i<hossz ; i++ ) if ( legkisebb > szam[i] ) legkisebb = szam[i]

Ilyen módon egyszer kell végigmenni az összes számjegyen, számjegyenként pontosan egy összehasonlítás van.

Szerintem ti értitek félre.

Nem egy számot kódoló STRING adott, hanem egy SZÁM. Ez mindenképpen érvényes, ha sikerült ábrázolni. Semmilyen begépelt karakterekről vagy karaktersorozatról nem volt szó. A szám az egy absztrakt dolog, valamilyen számrendszerben lehet ábrázolni, hogy megfoghatóbb legyen. Én egy általános algoritmust akartam írni, akinek kényelmesebb nyugodtan képzelhet b helyébe 10-et, de akár 16-ot vagy 812-őt is.

> „a kutyát nem érdekli, hogy ez egy szám.”

Vesd össze:

> „Algoritmus amely meghatározza egy természetes szám legkisebb számjegyét.”

Te most azt mondtad, hogy a kutyát nem érdekli a feladat.

> „egyszerűen írni kell egy cserélgetős nagyság szerint sorba rendező algoritmust”

Senki nem kérte, hogy rendezz sorba, csak egy minimum megkeresése volt a feladat, az pedig az elemek száma mínusz egy összehasonlítással simán megoldható. Persze lehet rendezni is, ha ráérsz, bár a számok (sőt, a karakterek is) eleve rendezve vannak.

> „De mint írták előttem, maximum annak az ellenőrzésében van szerepe a számrendszernek, hogy a szám érvényes szám-e.”

Azt írták, hogy van egy szám. Az nem szokott feladat lenni, hogy eldöntsük egy adott számról, hogy szám-e.

> „Nem kell elosztani a számrendszer alapjával, hiszen a 2 az 2, akár tízes, akár nyolcas, akár tizenhatos számrendszerben nézem.”

Igen, ezt magyarázom én is, hogy a 2 az kettő, de kettes számrendszerben felírva a legkisebb jegye k*vára nem ugyanaz, mint tízes vagy 3-as számrendszerben. 12 is tizenkettő, akár úgy írom, hogy C, akár úgy hogy 1100, de a legkisebb jegye más. Még akkor is tizenkettő, ha úgy írom, hogy dodeka vagy hogy zwölf. Nem értem, hogy miért karaktersorozatként akartok elképzelni egy számot. Ennyi erővel a 'tizenkettő' ábécérendben első betűjét is vehetnénk a legkisebb számjegynek, ami 'e' (illetve 'a' vagy 'f').

> „legkisebb = szam[0]

hossz = strlen(szam)

for ( i=1 ; i<hossz ; i++ ) if ( legkisebb > szam[i] ) legkisebb = szam[i]”

Ezt javasoltam én is, csak én az utolsó jegytől megyek végig, és a számot SZÁMKÉNT kezelem, nem pedig versként…

Hát pedig a számítógép tárolja valamilyen típusban a számot. Ha számról, absztrakt fogalomról van szó, akkor annak nincs számrendszere. A számrendszer csak a felíráshoz kell, ahhoz, hogy a számot – mint értéket, absztrakt fogalmat – jelsorozattá – számjegyek sorozatává – alakítsuk.

Tehát ha absztrakt fogalomként tekintünk rá, akkor nem értelmezhető a számjegy, mint fogalom.

Ha viszont számjegyek sorozataként tekintünk rá – ahol már értelmezhető a számjegy fogalma –, akkor meg ezek már csak jelek, aminél a jelek sorrendisége számít csak, a ténylegesen képviselt értékük másodlagos. (Persze elvileg nem lényegtelen hiszen pont ez határozza meg a sorrendjüket.)

Minden valamirevaló programnyelvben van szám→karakterlánc konverzió, amivel jóval egyszerűbben megoldható a feladat. Ha a szám történetesen mondjuk egy egész típusú változóban van, akkor jóval egyszerűbb átkonvertálni stringgé, és úgy megoldani, ahogy megoldottam.

Annyi igaz, hogy ha valóban mondjuk long típusban van meg a szám, és nagyon szűk a memória, valamint nagyon kritikus a futási sebesség, akkor a megoldásod optimálisabb, de kicsit a feladat túlgondolásának tartom, persze ízlések és pofonok ugye…

Egyébiránt azt kell mondanom, hogy tulajdonképpen a feladat nincs jól specifikálva.