Rekurzije i slične boljke
Select messages from
# through # FAQ
[/[Print]\]

Forum@DeGiorgi -> Programiranje 1 i 2

#1: Rekurzije i slične boljke Autor/ica: krilo PostPostano: 14:42 sri, 8. 3. 2017
    —
Pozdrav ekipi Very Happy
Imam jedan zadatak iz dz kojeg polovično znam riješiti bez rekurzije, ali to nije nažalost ono što se traži. Zbunjen
Napišite program koji učitava prirodni broj k<9, te niz od k različitih dekadskih znamenaka. Ukoliko učitane znamenke nisu različite, program treba ispisati poruku "Greska!" (bez navodnika). Program treba ispisati sumu svih prirodnih brojeva čije su znamenke iz učitanog niza, te se ne ponavljaju unutar jednog broja.

Na primjer, za k = 2 i učitane brojeve 1 i 3, program ispisuje "48" (jer je 1+3+13+31=48 ).

Znam napisati program koji računa (i radi!) traženu sumu za sve brojeve (iste i različite unesene), ali ne znam kako bih provjerila traženi uvjet. Išla sam za idejom da rastavljam brojeve i onda ih zbrajam (u gornjem primjeru: 1+3+13+31=1+1+10+3+3+30) pomoću funkcije sum.
To je što sam pokušala. Kako riješiti problem rekurzijom, nemam pojma. Ako netko ima ideju, neka podijeli, ne treba kod. Hvala Smile

Kod:
#include <stdio.h>
#include <stdlib.h>

int pot(int x, int y)
{
    int i, prod=1;
    for (i=0; i<y; i++) prod*=x;
    return prod;
}

int sum(int k, int n)
{
    int i, suma=0;
    for (i=0; i<k; i++) suma+=n*pot(10,i);
    return suma;
}

int main(void)
{
    int k, i, n, suma=0;
    scanf ("%d", &k);

    for (i=0; i<k; i++)
        {
            scanf ("%d", &n);
            suma+=sum(k,n)+n;
        }
    printf ("%d", suma);

    return 0;
}

#2:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 17:39 sri, 8. 3. 2017
    —
Ako dobro citam,
[dtex]\operatorname{sum}(k, n) = \sum_{i=0}^{k-1} n * 10^i = n * \underbrace{11\cdots1}_k = \underbrace{nn\cdots{}n}_k.[/dtex]
Kakve to veze ima sa zadatkom?

Pogledaj u skripti zadatak 2.3.3 i ponesto zadataka iza njega. Ovdje nas zanima suma svih brojeva koji se sastoje od svih ili nekih ucitanih znamenaka. Dakle, treba
  1. naci sve neprazne podskupove ucitanog skupa brojeva (to su skupovi znamenaka za svaki razmatrani sumand);
  2. za svaki podskup naci sve moguce redoslijede (permutacije), sto nam daje same sumande;
  3. od svakog redoslijeda sloziti broj (to je stvarni sumand) i dodati ga u sumu.
U terminima zadatka:
  1. Moguci skupovi znamenaka: [tex]\{ \{1\}, \{3\}, \{1,3\} \}[/tex]
  2. Svi moguci redoslijedi znamenaka:
    • za znamenke iz skupa [tex]\{1\}[/tex]: [tex][1][/tex];
    • za znamenke iz skupa [tex]\{3\}[/tex]: [tex][3][/tex];
    • za znamenke iz skupa [tex]\{1,3\}[/tex]: [tex][1,3][/tex] i [tex][3,1][/tex].
  3. Dakle, brojevi su [tex]1,3,13,31[/tex].
Dozvoljeno je razbiti na dvije rekurzije (posebno podskupovi, posebno permutacija svakog podskupa) ili pokusati sloziti jednu.

#3:  Autor/ica: phy PostPostano: 19:42 pet, 10. 3. 2017
    —
...

#4:  Autor/ica: krilo PostPostano: 15:12 uto, 14. 3. 2017
    —
Suma iz zadatka ([tex]\sum_{i=1}^{k-1}n \cdot 10^i[/tex]) je trebala funkcionirati po principu 1+3+13+31=1+3+11+33, ali daljnjom provjerom nalazim da očito ne štima.
Odslušala sam još predavanja i pogledala sve primjere u skripti, probala s nekim inačicama istih, ali ništa od toga. Jasan mi je zadatak 2.3.3. i kako se napiše rekurzija kada treba provjeriti djeljivost sume, ali kako da ja na ovom primjeru rastavim skup na podskupove, zaista ne znam. Na skoro svim sličnim primjerima iz skripte ili s predavanja traži se ili prebrojavanje podskupova ili provjeravanje nekih uvjeta ili mijenjanje elemenata niza, a ovo je pak rastavljanje skupa na manje dijelove.
Permutacije i konstrukciju brojeva bih vjerojatno i znala, ali otom potom. Korak 1 je problem.

#5:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 14:24 sri, 15. 3. 2017
    —
Alociraj dodatni niz. U rekurziji ces mu ili dodatvati elemente ili neces (dvije grane). Pseudo-kod:

Kod:
function rek(input, n, subset=[], m=0):
    if n == 0:
        napravi nesto s podskupom i izadji iz rekurzije
    n--
    # Rekurzija za podskupove koji ne sadrzavaju zadnji element input-a
    rek(input, n, subset, m)
    # Rekurzija za podskupove koji sadrzavaju zadnji element input-a
    rek(input, n, subset + [input[n]], m+1)


Dakle:
  1. Kad je input prazan, nemamo sto s njim raditi, sto znaci da je podskup subset skroz kreiran.
  2. Podskup u koji ne dodajemo nista je jednak ovome koji imamo, no rekurzija se poziva sa smanjenim n, sto je ekvivalent micanju zadnjeg elementa iz input-a (jer mu je n duljina).
  3. Podskup u koji dodajemo input[n] ima element vise, sto znaci da ga treba ubaciti u niz subset koji sadrzi elemente podskupa (pseudo-zapisano kao subset + [input[n]] i povecati mu duljinu (m+1).
Inicijalne vrijednosti subset-a i m opisuju prazni skup (ali u ANSI C-u ih ne smijes ovako navesti, no to je sitna tehnikalija).

Nadam se da je sada jasnije.

#6:  Autor/ica: krilo PostPostano: 22:05 pet, 17. 3. 2017
    —
Hvala, jasnije mi je sad, samo me još jedna stvar kopka: ovo kad staviš rek(input, n, subset=[], m=0) pri pravljenju funkcije, što je točno subset=[] u svemu tome? Nepoznato mi je stavljanje znaka jednakosti u deklaraciju funkcije. Koja je uloga ovih zagrada oko input[n] u subset + [input[n]]? Molim te, elaboriraj ako ti nije problem. Je li to baš postupak premještanja članova iz niza u niz ili nešto drugo?

#7:  Autor/ica: mdokoLokacija: Heriot-Watt University, Edinburgh PostPostano: 11:17 sub, 18. 3. 2017
    —
krilo (napisa):
ovo kad staviš rek(input, n, subset=[], m=0) pri pravljenju funkcije, što je točno subset=[] u svemu tome? Nepoznato mi je stavljanje znaka jednakosti u deklaraciju funkcije.

Odgovor imaš u prethodnom vseginom postu:
vsego (napisa):
Inicijalne vrijednosti subset-a i m opisuju prazni skup (ali u ANSI C-u ih ne smijes ovako navesti, no to je sitna tehnikalija).


Citat:

Koja je uloga ovih zagrada oko input[n] u subset + [input[n]]? Molim te, elaboriraj ako ti nije problem. Je li to baš postupak premještanja članova iz niza u niz ili nešto drugo?

Već je elaborirano u prethodnom postu:
vsego (napisa):
Podskup u koji dodajemo input[n] ima element vise, sto znaci da ga treba ubaciti u niz subset koji sadrzi elemente podskupa (pseudo-zapisano kao subset + [input[n]] i povecati mu duljinu (m+1).

#8:  Autor/ica: krilo PostPostano: 21:10 sub, 18. 3. 2017
    —
Hvala. Izgleda da mi baš ne polazi za rukom objasniti što mi nije jasno, pa ću se još konzultirati sa svojim asistentom. Predajem se...

#9:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 13:14 pon, 20. 3. 2017
    —
krilo (napisa):
ovo kad staviš rek(input, n, subset=[], m=0) pri pravljenju funkcije, što je točno subset=[] u svemu tome? Nepoznato mi je stavljanje znaka jednakosti u deklaraciju funkcije.


To je inicijalna vrijednost. Hocu reci da kod prvog poziva trebas postaviti subset na prazni niz. S obzirom da m oznacava duljinu, zapravo subset ne treba nista posebno, ali ja volim biti precizan.

krilo (napisa):
Koja je uloga ovih zagrada oko input[n] u subset + [input[n]]? Molim te, elaboriraj ako ti nije problem. Je li to baš postupak premještanja članova iz niza u niz ili nešto drugo?


Posto je subset niz, onda subset + input[n], i.e., "niz plus broj", nema puno smisla, pa sam stavio subset + [input[n]], sto aludira na konkatenaciju nizova. Dakle, [x] mi je jednostavno pokrata za "jednoclani niz koji sadrzi x". Pythonovska notacija; C-ovska bi bila {x}, no to mi se cini konfuzno jer lici na matematicke skupove, a i nisam htio da kod izgleda previse C-ovski jer se nista od toga ne smije bukvalno prepisati.

Nadam se da je sada jasnije.

#10: String issue Autor/ica: krilo PostPostano: 12:37 uto, 11. 4. 2017
    —
Pozdrav Smile
Imam problem s funkcijom koja barata stringovima: okreni_i_nalijepi prima neki string, integere i i t, u danom stringu izdvaja i okreće podstring od t-tog do i-tog mjesta, te ga lijepi nazad na isto mjesto. Npr. za string dva i tri, i=7, t=4, pretvara string u dva rt ii jer je string[7]=r i string[4]=i. Koristim se funkcijom okreni koja samo okreće dani string i funkcionira (po svemu sudeći; stavljam je na dno posta jer mislim da ona nije problem).

Kod:
void okreni_i_nalijepi(char *string, int i, int t)
{
    char *tstring; int j;
    tstring=(char*)malloc(sizeof(char)*(i-t+1));
    for (j=0; j<i-t+1; j++) tstring[j]=string[t+j];
   
    okreni(tstring);
   
    int k=0;
    for (j=t; tstring[k]!='\0'; j++) {string[j]=tstring[k++];}
    free(tstring);
    return;
}


Problem je u tome što kad, nakon što ubacim kontrolni ispis nakon prve for-petlje, izbacuje dobar tstring (temporary-string), ali njemu na kraj nakelji neki čudan "L" znak koji mi poremeti cijeli proces. Probala sam umjesto (i-t+1) u uvjetu petlje staviti samo (i-t), ali to onda nepravilno skrati string. Ideas?

Funkcija "okreni":
Kod:
void okreni(char *s)               
{
    int k=0, p, i; char *t; t=s;
    p=strlen(s)-1;
    t=(char*)malloc(sizeof(char)*(p+1));
    for (i=0; i<p+1; i++) *(t+i)=*(s+i);
    int r=p+1;
    while (r--)
        {s[k++]=t[p--];}
    free(t);
}

#11:  Autor/ica: mdokoLokacija: Heriot-Watt University, Edinburgh PostPostano: 14:18 uto, 11. 4. 2017
    —
Koliko ja vidim, nigdje ne staviš '\0' na kraj stringa tstring.



P.S. Algoritam ti je dobar, ali malkice kompliciran. Naime, ne trabaju ti nikakvi pomoćni stringovi. Baci pogled na ovu implemetaciju tvoje funkcije:
Kod:
void okreni_i_nalijepi(char *string, int i, int t) {
  while (t < i) {
    char tmp = string[i];
    string[i] = string[t];
    string[t] = tmp;
    t = t + 1;
    i = i - 1;
  }
}

#12:  Autor/ica: krilo PostPostano: 12:42 ned, 23. 4. 2017
    —
Evo dočekah konačno i zadnju provjeru iz aplikacije... naravno da program ne valja. I to, naravno, kad se ubaci protuprimjer stringa od milijun znakova (iako ne vidim razloga zašto ne bi program i tada radio). Možda je čak i program dobar, ali mi aplikacija neće prihvatiti ni najjednostavniji zadatak koji radi bez problema...

Napišite program koji učitava jednu riječ s najviše 13467 znakova, te ispisuje koliko se puta u toj riječi pojavljuje podstring "uz".
Kod:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int prebroji(char *s)
{
    int brojac=0;
    while (*s!='\0')
        {if (*s=='u')
            if (*(s+1)=='z') brojac++;
         s++;}

    return brojac;
}

int main(void)
{
    char *string;
    string=(char*)malloc(sizeof(char)*13468);
    gets(string);
    printf ("%d\n", prebroji(string));
    free(string);

return 0;
}


U čem je kvaka? Ja to stvarno ne znam

(P.S. hvala na uputi mdoko za alternativnu implementaciju funkcije, sjećam se da smo ju na predavanjima radili, ali mi nije zazvonilo Smile )

#13:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 14:08 ned, 23. 4. 2017
    —
Ne ucitavas jednu rijec nego cijelu liniju. Kladim se da taj string od "milijun" znakova ima barem jedan razmak u sebi.

#14:  Autor/ica: krilo PostPostano: 16:22 ned, 23. 4. 2017
    —
E hvala, konačno ga je prihvatio... i još vezano za postavljanje zadatka, ako u zadatku piše da "program treba izbrisati svaku sedmu riječ", podrazumijeva li to da se maknu samo slova ili i jedan ekstra razmak koji ostane kad se obrišu slova?

#15:  Autor/ica: vsegoLokacija: /sbin/init PostPostano: 17:24 ned, 23. 4. 2017
    —
Nije bitno. Verifikator visestruke razmake tretira kao jedan.

Korisno je pogledati input na kojem je rjesenje palo i vidjeti brise li tvoj program rijeci koje treba i da li stvarno izokrece sve ostale. Jasno, neces gledati cijeli ogromni input, ali recimo do druge-trece rijeci koju treba obrisati + od zadnje ili predzadnje takve do kraja inputa je obicno dovoljno. Greske se vrlo rijetko dogadjaju samo u sredini.

Usput, kakve sve ovo veze ima s rekurzijama? Koliko znam, otvaranje novog topica se ne naplacuje...

#16:  Autor/ica: krilo PostPostano: 13:52 pon, 24. 4. 2017
    —
A ono, promijenim samo naslov posta pa se pravim da se to broji... Very Happy Ajde vec ako je red, otvorit cu novi topic za pointere.



Forum@DeGiorgi -> Programiranje 1 i 2


output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.

Powered by phpBB © 2001,2002 phpBB Group
Theme created by Vjacheslav Trushkin