Stefan Sokołowski, Podstawy programowania
LABORATORIUM 14

Zadanie 0:

Przez ,,wyszukanie'' jakiegoś x w jednowymiarowej tablicy a rozumie się znalezienie takiego indeksu i , że

x

a[i]

lub zasygnalizowanie, że takiego elementu w tablicy nie ma.

Żeby móc wyszukiwać, potrzebujemy funkcji porównującej elementy — czy to ten element, czy inny — to nie zawsze oznacza identyczność. Na przykład funkcja

  int ten_sam(char a[], char b[]) {
    /* porownanie napisow
     * (wymaga  #include<string.h> )
     */
    if (strlen(a) != strlen(b))  return 0;
    else {
      i=0;
      while (i<strlen(a) && a[i]==b[i]) i++;
      return  (i==strlen(a));
    }
  }

traktuje jako ,,te same'' napisy identyczne; a funkcja

  int ten_sam(double a, double b) {
    /* porownanie liczb rzeczywistych
     * z dokladnoscia do 0.001
     */
    return  a-b<0.001 && b-a<0.001;
  }

uważa za ,,te same'' dwie liczby różniące się o mniej niż jedna tysięczna.

Proszę uruchomić program, który wczyta (do tablicy) 100 000 liczb całkowitych z pliku plik1 , a następnie wczyta liczbę z klawiatury i wyszuka ją w tablicy: wyświetli

albo jej pozycję w tablicy,
albo informację, że jej w tablicy nie ma.

Wskazówka:
Ponieważ mamy czytać raz z pliku, a drugi raz z klawiatury, nie możemy skorzystać z przekierowania wejścia dla całego programu. Ale funkcja

  void wczyt(char nazwa_pliku[], int tablica_docelowa[], int n) {
    // wymaga  #include<stdlib.h>
    FILE* ff = fopen(plik, "r");
    if (ff == NULL) {
      printf("\n  Plik %s nie istnieje lub jest niedostepny\n", nazwa_pliku);
      exit(1);
    }
    else {
      for (int i=0; i<n; i++)
        fscanf(ff, "%i", &tablica_docelowa[i]);
      fclose(ff);
    }
  }

wczytuje liczby całkowite z pliku dyskowego do tablicy. Nie trzeba znać szczegółów tej funkcji, wystarczy wiedzieć, jak ją wywołać. Na przykład komenda

  wczyt("abc", liczby, 1000);

powoduje wczytanie 1000 liczb z pliku o nazwie abc do tablicy liczby . Ta tablica musi być zadeklarowana jako całkowita i mieć długość co najmniej 1000. Plik abc musi znajdować się w tym samym katalogu, w którym mieści się wykonywalny przekład programu.

Zadanie 1:

Proszę uruchomić program, który wczyta (do tablicy) 100 000 liczb całkowitych z pliku plik1 (por. zad. 0) oraz (do innej tablicy) 10 000 całkowitych liczb z pliku plik2 , następnie policzy, ile liczb występuje zarówno na jednym jak na drugim pliku.

Wskazówka:
Oczywiście dla rozwiązania tego zadania trzeba będzie dwukrotnie wywołać funkcję wczyt z odpowiednio zmienionymi parametrami. Kiedy już wczytamy do tablic liczby z obu plików, można w pętli po mniejszej tablicy wyszukiwać kolejną liczbę w większej tablicy i zwiększać licznik, jeśli się tam znajdzie.

Zadanie 2:


Skopiowane z `Wikipedii`.

Sortowanie bąbelkowe działa tak, że każdy element tablicy jest kolejno porównywany z następnym i

jeśli porządek jest zachowany, to nic się z nimi dzieje,
jeśli element wcześniejszy jest większy od późniejszego, to te elementy są zamieniane,

i tablica jest przeglądana dalej. W wyniku takiego przebiegu największy element tablicy na pewno znajdzie się na końcu, więc następny przebieg przez nią może być o jeden element krótszy.

Uwaga: Na sortowanie składają się dwie zagnieżdżone pętle:

zewnętrzna, sterująca kolejnymi przebiegami; oraz
wewnętrzna, zamieniająca elementy wewnątrz przebiegu.

Przebiegi są coraz krótsze, więc zakres działania wewnętrznej pętli powinien być coraz mniejszy. Jednak w internecie można znaleźć prezentacje, w których granice działania wewnętrznej pętli nie zmieniają się. Proszę pamiętać, że to jest wersja wadliwa. Tak zorganizowany program wielokrotnie sprawdza porządek par elementów, które już na pewno są dobrze ustawione i nie ma po co ich sprawdzać.

Proszę napisać program, który wczyta 10 000 liczb całkowitych z pliku plik2 (por. zad.1), posortuje je bąbelkowo, a następnie wypisze do innego pliku. Oto funkcja realizująca pisanie liczb całkowitych z tablicy do pliku dyskowego:

  void pisz(char nazwa_pliku[], int tablica_zrodlowa[], int n) {
    // wymaga  #include<stdlib.h>
    FILE* ff = fopen(nazwa_pliku, "w");
    if (ff == NULL) {
      printf("\n  Nie mozna pisac do pliku %s \n", plik);
      exit(1);
    }
    else {
      for (int i=0; i<n; i++)
        fprintf(ff, "%i\n", tablica_zrodlowa[i]);
      fclose(ff);
    }
  }

Powtórzyć takie samo sortowanie dla 100 000 liczb całkowitych z pliku plik1 , ale uwaga! — sortowanie pliku 10-krotnie większego może trwać 100-krotnie dłużej.

Zadanie 3:

W pliku plik3 zapisane jest 100 000 słów (wygenerowanych losowo, więc bez sensu) o długości do 15 liter; a w pliku plik4 zapisane jest 10 000 takich słów. Proszę uruchomić program wczytujący te słowa do tablic, a potem sprawdzający, ile z nich występuje w obu plikach (por. zad. 1).

Wskazówka:
Funkcja

  void wczyt(char nazwa_pliku[], char tablica_docelowa[][dlug_max], int n) {
    // wymaga  #include<stdlib.h>
    FILE* ff = fopen(nazwa_pliku, "r");
    if (ff == NULL) {
      printf("\n  Plik %s nie istnieje lub jest niedostepny\n", nazwa_pliku);
      exit(1);
    }
    else {
      for (int i=0; i<n; i++)
        fscanf(ff, "%s", tablica_docelowa[i]);
      fclose(ff);
    }
  }

wczytuje n słów (o długości mniejszej niż dlug_max ) z pliku nazwa_pliku do tablicy tablica_docelowa .

Zadanie 4:

Proszę napisać program, który wczyta 10 000 słów z pliku plik4 , posortuje je alfabetycznie metodą bąbelkową (por. zad.2), a następnie wypisze do innego pliku. Oto funkcja realizująca pisanie n słów z tablicy spis do dyskowego pliku plik :

  void pisz(char nazwa_pliku[], char tablica_zrodlowa[][dlug_max], int n) {
    // wymaga  #include<stdlib.h>
    FILE* ff = fopen(nazwa_pliku, "w");
    if (ff == NULL) {
      printf("\n  Nie mozna pisac do pliku %s\n", nazwa_pliku);
      exit(1);
    }
    else {
      for (int i=0; i<n; i++)
        fprintf(ff, "%s", tablica_docelowa[i]);
      fclose(ff);
    }
  }

Wskazówka:
Oczywiście będzie potrzebne porównanie napisów ze względu na porządek alfabetyczny:

  int alfab(char napis1[], char napis2[]) {
    /* porownanie ALFABETYCZNE napisow
     * (wymaga  #include<string.h> )
     */
    int i=0;
    while (i<strlen(napis1) && i<strlen(napis2) && napis1[i]==napis2[i])
      i++;
    if (i<strlen(napis1) && i<strlen(napis2)) {
      // wyszlismy z petli dlatego, ze napisy roznia sie  i -tym znakiem
      if (napis1[i] < napis2[i])  return -1;
      else  return 1;
    } else {
      // wyszlismy z petli dlatego, ze  i  doszło do konca ktoregos napisu
      if (strlen(napis1) == strlen(napis2))  return 0;
      else  if (strlen(napis1) < strlen(napis2))  return -1;
            else  return 1;
    }
  }

Funkcja alfab zwraca

0 — jeśli oba napisy są równe,
-1 — jeśli napis1 alfabetycznie poprzedza napis2 ,
1 — jeśli napis2 alfabetycznie poprzedza napis1 .

Zamiast niej można użyć bibliotecznej funkcji strcmp . Ona również potrzebuje #include<string.h> .

Zadanie 5:

Wyszukiwanie takie jak w zad. 0 przypomina szukanie nazwiska w książce telefonicznej w taki sposób, że czytamy wszystko od pierwszej strony do ostatniej sprawdzając, czy trafiliśmy na to, którego potrzebujemy. Oczywiście nikt tak nie robi. Ponieważ nazwiska w książce telefonicznej są uporządkowane alfabetycznie, możemy znacznie przyspieszyć szukanie w ten sposób, że

sprawdzamy czy szukane nazwisko jest wcześniejsze czy późniejsze od nazwiska w środku książki;
jeśli jest wcześniejsze, to skupiamy się na pierwszej połowie książki, jeśli późniejsze, to na drugiej; i znowu porównujemy szukane nazwisko ze środkowym z odpowiedniej połowy
za każdym razem fragment książki, w którym może być szukane nazwisko, maleje o połowę; w końcu ten fragment zmaleje do długości 1.

Proszę zaprogramować wyszukiwanie

liczby w uporządkowanej tablicy liczb, oraz
napisu w alfabetycznie uporządkowanej tablicy napisów

opisaną wyżej metodą binarną.

Wskazówka:

int znajdz(typ x, typ tab[kon]) {
  int pocz=0;
  if (mniejszy(x, tab[pocz]) || mniejszy(tab[kon-1], x))
    return 0;
  else {
    // teraz:   tab[pocz] ≤ x < tab[kon]
    while (pocz+1<kon) {
      int srodek = (pocz+kon)/2;
      if (mniejszy(x, tab[srodek]))  kon = srodek;
      else  pocz = srodek;
    }
    return (ten_sam(x, tab[pocz]));
  }
}

Oczywiście czerwone elementy powyżej należy zamienić na właściwe, zależnie od typu szukanych elementów.

Do mojej głównej witrynki

Ostatnia modyfikacja: 25 stycznia 2025