[C]Zawieranie się tablicy

exevan
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 25 lut 2014, o 21:16
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 6 razy

[C]Zawieranie się tablicy

Post autor: exevan »

Witam, mam takie zadanie:
Napisz program, ktory zapelnia tablice
- A o rozmiarze N=100 oraz tablice
- B o rozmiarze N=5
wartosciami losowymi. Nastepnie program sprawdza czy tablica B zawiera sie w tablicy A
(nalezy sprawdzic, czy w tablicy A wystepuja takie same wartosci i w takiej samej kolejnosci jak w tablicy B - ewentualnie ile razy wystepuja).
To co napisałem do tej pory:

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <moje_funkcje.h>

#define A 6
#define B 2

void Uzupelnij_Tablice(int Nazwa_Tab[],int Wielkosc_Tab, int Przedzial)
{
    int i;
    for(i=0;i<Wielkosc_Tab;i++)
    {
        Nazwa_Tab[i] = rand()%Przedzial;
    }
}

void Wypisz_Tablice(int tab[], int size)
{
    int i;
    for(i=0;i<size;i++) printf("[%d]%d	",i,tab[i]);
}

void Sprawdz_Wzorzec(int Nazwa_Tab_A[], int Tab_Wzorzec[], int Wielkosc_Tab_A, int Wielkosc_Tab_B)
{
    int i,j,temp=0;
    for(i=0;i<Wielkosc_Tab_A;i++)
    {
        printf("A: %d
",i);
        for(j=0;j<Wielkosc_Tab_B;j++)
        {
            printf("B: %d
",j);
			if(Tab_Wzorzec[j] == Nazwa_Tab_A[i])
			{
				temp = temp + 1;
				i++;
				if(temp == Wielkosc_Tab_B)
                {
                    printf("Tablica B zawiera sie w A.");
                    break;
                }
            } else j=0;
        }

    }
}

int main()
{
    srand( (unsigned int)time(NULL) );
    int tab_A[A], tab_B[B];
    system("cls");
	Uzupelnij_Tablice(tab_A,A,5);
	Uzupelnij_Tablice(tab_B,B,5);

    Wypisz_Tablice(tab_A,A);
    printf("
");
    Wypisz_Tablice(tab_B,B);

    Sprawdz_Wzorzec(tab_A,tab_B,A,B);

	system("pause");
    return 0;
}
No i są błędy.. Moim pomysłem na to zadanie było mniej więcej takie działanie:

Kod: Zaznacz cały

1. Sprawdź czy 0 element tablicy B jest równy 0 elementowi tablicy Jeśli:
    Tak:  Sprawdz czy 1 element tablicy B jest równy 1 elementowi tablicy A.
            Tak: Sprawdz czy 2 element tablicy B jest równy 2 elementowi tablicy A.
            Nie: Sprawdz czy 0 element tablicy B jest równy 3 elementowi tablicy A.
    Nie: Sprawdź czy 0 element tablicy B jest równy 1 elementowi tablicy A. 
           Tak: Sprawdz czy 1 element tablicy B jest równy 2 elementowi tablicy.
I tak dalej.

Mam nadzieje że ktoś zrozumie to co napisałem. Myślałem o wykorzystaniu sortowania bąbelkowego ale nie do sprawdzania większości tylko równości. Proszę o pomoc
Awatar użytkownika
jarzabek89
Użytkownik
Użytkownik
Posty: 1337
Rejestracja: 11 lis 2007, o 21:36
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 4 razy
Pomógł: 181 razy

[C]Zawieranie się tablicy

Post autor: jarzabek89 »

Jestem słaby w analizowaniu cudzego kodu, ale nie podoba mi się 36linijka.
Zakładamy że pierwszy element z tablicy A równy jest elementowi pierwszemu z tablicy B.

Kod: Zaznacz cały

if(Tab_Wzorzec[j] == Nazwa_Tab_A[i])
Warunek ten zostanie spełniony.
Wykona się:

Kod: Zaznacz cały

 i++;
Zakładamy że kolejne sie nie zgadzają. Pętla for, tam gdzie są j, wykona się bezsensownie jeszcze pare razy, ale co najważniejsze zmienna i zostanie zwiększona o 1 czasami o 2, czasem o 4 w pętli for, tam gdzie jest j. For z j się kończy i wracamy do pierwszego fora, i zamiast równać się 1 będzie równało się 3, 4. Omijane są liczby z tablicy A.
Brakuje sporo w Twoim kodzie.
Gouranga
Użytkownik
Użytkownik
Posty: 1565
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 243 razy

[C]Zawieranie się tablicy

Post autor: Gouranga »

pytanie jeszcze czy te elementy mogą być rozrzucone po tablicy, tzn. czy w tablicy [1 2 3 4 5] zawiera się np. tablica [1 3 5]
jeśli tak to zadanie się nieco komplikuje
Andreas
Użytkownik
Użytkownik
Posty: 1130
Rejestracja: 1 lis 2008, o 22:33
Płeć: Mężczyzna
Podziękował: 72 razy
Pomógł: 156 razy

[C]Zawieranie się tablicy

Post autor: Andreas »

Poprawiłem trochę kod programu, ale są to drobne kosmetyczne zmiany, dla czytelności.
Ukryta treść:    
Funkcja Sprawdz_wzorzec nie działa poprawnie. Proponuję ci przepisać ją od nowa, najlepiej z wykorzystaniem algorytmu Boyera i Moore'a - nie ma potrzeby sprawdzania każdego znaku z osobna.

else j=0; - tu jest błąd - w przypadku gdy warunek nie jest spełniony, ustawia j na 0 i sprawdza kolejny raz to samo, w nieskończoność.
exevan
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 25 lut 2014, o 21:16
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 6 razy

[C]Zawieranie się tablicy

Post autor: exevan »

Dlatego mam problem. Wiem jak chce żeby działał mój program, ale nie mam pojęcia jak to wykorzystać przy pisaniu...

Mniej wiecej tak:

Kod: Zaznacz cały

[4, 5, 2, 7, 9]
[2, 7]
1 krok: 2==4 ? NIE
[4, 5, 2, 7, 9]
    [2, 7]
2 krok: 2==5 ? NIE
[4, 5, 2, 7, 9]
       [2, 7]
3 krok: 2==2 ? TAK
[4, 5, 2, 7, 9]
       [2, 7]
4 krok: 7==7 ? TAK
5 krok: czy tablica B ma wiecej elementow ? NIE // ten krok sprawdzany jest co każdą iteracje
Tab B zawiera sie w tab A, koniec programu
Muszą być w tej samej kolejności. Na szczęście
Andreas
Użytkownik
Użytkownik
Posty: 1130
Rejestracja: 1 lis 2008, o 22:33
Płeć: Mężczyzna
Podziękował: 72 razy
Pomógł: 156 razy

[C]Zawieranie się tablicy

Post autor: Andreas »

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int A=12;
int B=2;

void Uzupelnij_Tablice(int Nazwa_Tab[],int Wielkosc_Tab, int Przedzial)
{
    int i;
    for(i=0;i<Wielkosc_Tab;i++)
    {
        Nazwa_Tab[i] = rand()%Przedzial;
    }
}

void Wypisz_Tablice(int tab[], int size)
{
    int i;
    for(i=0;i<size;i++) printf("%d ",tab[i]);
}

bool Sprawdz_Wzorzec(int Tab_A[], int Tab_Wzorzec[], int Wielkosc_Tab_A, int Wielkosc_Tab_B)
{
    int temp,ile;
    for (int a=0; a<Wielkosc_Tab_A; a++)
    {
        ile=0;
        temp=a;
        for (int b=0; b<Wielkosc_Tab_B; b++)
        {
            if (Tab_A[temp]==Tab_Wzorzec[b])
            {
                temp++; // przesuwamy sie o 1 w prawo w tablicy A
                ile++; // ile z elementow wzorca sie zgadza
            }
        }
        //printf("a = %d, ile = %d
",a,ile);
        if (ile==Wielkosc_Tab_B) // jesli caly wzorzec wystepuje w tablicy A
            return 1;            // to zwracamy 1 i konczymy
    }
    return 0;
}

int main()
{
    srand( (unsigned int)time(NULL) );
    int tab_A[A], tab_B[B];
    system("cls");
    Uzupelnij_Tablice(tab_A,A,5);
    Uzupelnij_Tablice(tab_B,B,5);

    printf("A[i]= ");
    Wypisz_Tablice(tab_A,A);
    printf("
");
    printf("B[i]= ");
    Wypisz_Tablice(tab_B,B);
    printf("

");

    if (Sprawdz_Wzorzec(tab_A,tab_B,A,B))
        printf("Tablica B zawiera sie w A.");
    else
        printf("Tablica B NIE zawiera sie w A.");
    return 0;
}
exevan
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 25 lut 2014, o 21:16
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 6 razy

[C]Zawieranie się tablicy

Post autor: exevan »

Oo dzięki wielkie W sumie byłem blisko widzę kilka poprawek i dodanie zmiennej dodatkowej.
ODPOWIEDZ