Rekurzija,rekurzija....!!!!

[ MrLimeni @ 12.02.2005. 09:01 ] @

Ovako ljudi... Ovaj zadatak nam vec nekoliko rokova dolazi,i niko od nas ga nije uspio rijesiti u potpunosti. Treba ga rijesit rekurzivno. Ne kazem da se dobro snalazim u rekurziji,ali nisam ni toliko los. Inace mi radimo u c-u,ali bi mi bilo kakav algoritam dobro dosao. Evo sad zadatka.

Na javnim telefonskim aparatima u gradu MathProgramming na tipkama se pored brojeva nalaze i slova engleske abecede (osim Q i Z),kao na slici. Na primjer, broj 6378687 moze da pamti rijec NERVOUS. Napisati reurzivnu funkciju void StampajRijeci(char *s) koja stampa sve rijeci koje odgovaraju broju zadatom argumentom s.

------abc--def
--1----2----3

-ghi---jkl---mno
--4----5----6

-prs--tuv--wxy
--7----8----9

--------------
--*----0----#

Nisam znao kako bolje ovu sliku da prikazem ovako na brzinu..... Nadam se da cete je razumjeti....

[ jablan @ 12.02.2005. 11:23 ] @

Nešto na ovu foru, pišem iz glave u paskalu:

Code:

procedure recfun(startno: string; current: string)
var
    currcharindex, charindex: integer;
    digit, newchar: char;
begin
    if length(startno) = length(current) then
    begin
        writeln(current);
    end
    else
    begin
        currcharindex := length(current) + 1;
        digit := startno[currcharindex];
        for charindex := 1 to 3 do
        begin
            newchar := getcharfordigit(digit, charindex);
            recfun(startno, current + newchar);
        end;
    end;
end;

getcharfordigit je funkcija koja za unetu cifru vraca i-ti karakter (npr. getcharfordigit('2' i 2) je 'b', u tvom primeru). to napiši sam.

[ masetrt @ 12.02.2005. 11:47 ] @

ja ti saljem kao neki pseudo kod u kome racunam da imas namapirane po tri slova za jedan broj. Takodje sam umesto parametra u funkciji umesto stringa koristio int i uveo novi string parametar koji pamti sta je sve upisano za sada. Ovo je bukalno za dva minuta pa ako moze jos neko da pogleda ili ti istestiraj

function StampajRijeci(s : integer , npr : string) // kada pozivas f-ju npr treba da bude prazan
var a:integer;
npr1 , npr2 , npr3:string
begin
if (s <> 0)
begin
a := s mod 10;
s:= s div 10;
npr1 := "prvi namapiran za a" + npr;
StampajReci(s , npr1);
npr2 := "drugi namapiran za a" + npr;
StampajReci(s , npr2);
npr2 := "treci namapiran za a" + npr;
StampajReci(s , npr3);
end
else
begin
writeln(npr);//ovo ce posle svake reci da predje u novi red
end;
end;

[ Alef @ 12.02.2005. 12:23 ] @

Ovo je samo za brojeve od 1–9. Dopuni još za 0, #, *.

Code:

#include <stdio.h>
#include <ctype.h>
#include <string.h>

char *kod[] = { "---", "abc", "def", "ghi", "jkl", "mno",
        "prs", "tuv", "wxz" };

void StampajReci(char *s)
{
    char c;
    int i, n = 0, l;

    while (isalpha(s[n])) n++;
    l = strlen(s);

    if (l == n) {
        printf("%s\n", s);
    } else {
        c = s[n];
        for (i = 0; i < 3; i++) {
            s[n] = kod[c-'1'][i];
            StampajReci(s);
        }
        s[n] = c;
    }
}

int main()
{
    char *s = (char *) calloc(4, sizeof(char));
    strcpy(s, "234");
    s[3] = '\0';

    StampajReci(s);
    return 0;
}

Uf, tek sad vidim da su me preduhitrili .

[ Toyo @ 12.02.2005. 23:24 ] @

Ni jedao od ova tri resenja nije ispravno.

Prva dva ne postuju broj argumenata u funkciji koji treba da bude 1(verovatno je to poenta ovog zadatka).
Treci nece moci da radi sa brojem 0 i 1, posto te cifre ne treba da se menjaju u slova, vec samo prenesu, sto sa tim algoritmom nece moci.

Fora je da kada pozivas rekurziju sa samo tim jednim argumentom, da taj string praznis sa leve strane, a istovremeno i punis sa desne zamenjenim slovima. Izmedju njih se stavi neki separator naprimer blanko ili tacka.Kada je prvi karakter bas taj separator ti ispises kombinaciju.

Code:

procedure rekurzija(Broj:String);
const
     Cifra='000111abcdefghijklmnoprstuvwxy';
var
     c:Integer;
begin
     if pos(' ', broj)=1 then
        showmessage(Broj)
     else
         begin
              if pos(' ', Broj)=0 then
                 broj:=Broj+' ';
              c:=strtoint(copy(broj,1,1));
              broj:= copy(Broj, 2, Length(Broj)-1);
              rekurzija(Broj+cifra[c*3+1]);
              rekurzija(Broj+cifra[c*3+2]);
              rekurzija(Broj+cifra[c*3+3]);
         end;
end;

Eh da, u paskalu ako hoces da pristupis odredjenom karakteru u stringu, onda pocinjes od npr. Cifra[1] a ne Cifra[0] kao napr. u c-u, jer je Cifra[0] duzina stringa, pa prema tome za c treba prepraviti cifra[c*3+1]..[c*3+3] sa cifra[c*3+0] redom do [c*3+2].
Pozdrav

[ MrLimeni @ 15.02.2005. 12:42 ] @

Pozdrav ljudi...

Prvo da vam se zahvalim svima na pomoci. Nisam stigao prije da vam odgovorim jer spremam jedan ispit u citaonu pa nisam kuci po citav dan. Pregledao sam ove codove sto ste stavili i bas su mi pomogli. Ovdje je ostao jedini problem kako se tretiraju tipke "1" "0" "*" i "#". Ali ovo u zadatku nije precizno definisano tako da nema veze,lako bih se snasao sa tim.
Ovaj alefov kod sam prepravio malo (sitnice) i odlucio da ga okacim opet,jer ako se nadje neko ko trazi ovakav algoritam da ima sigurno tacan kod.
Usput uploadovao sam sliku koja prati ovaj zadatak kako bi bilo jasne sto se trazi (koliko je to moguce :-)...

jos jednom HVALA svima....

Code:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

char *kod[] = { "   ", "abc", "def", "ghi", "jkl", "mno",
        "prs", "tuv", "wxz" };

void StampajReci(char *s)
{
    char c;
    int i, n = 0, l;

    l = strlen(s);
    while ((isalpha(s[n])) || (s[n] == ' '))
        n++;

    if (n == l) {
        printf("%s\n", s);
    } else {
        c = s[n];
        if ((c == '0')||(c == '*')||(c == '#'))
        {
            s[n] = ' ';
            StampajReci(s);
        }
        else
        {
            for (i = 0; i < 3; i++) {
                s[n] = kod[c-'1'][i];
                StampajReci(s);}
        }
        s[n] = c;
    }
}

int main()
{
    char *s = (char *) calloc(4, sizeof(char));

    printf("Unesite broj: \n");
    gets(s);
    StampajRijeci(s);
    return 0;
}