Programowanie i algorytmy

Liczby kwadratowe

Zad. 1. W pliku kwadratowe.txt znajduje się 1000 liczb kwadratowych.

 

a) do pliku a.txt, skopiuj wszystkie liczby, których początkowe cyfry tworzące liczbę podniesioną do kwadratu dadzą tą liczbę np. 100 = 102.

b) do pliku b.txt skopiuj wszystkie liczby, w których istnieje taka kombinacja cyfr tej liczby, z których stworzona liczba podniesiona  do kwadratu da tą liczbę, np. 5476 = 742.

 

Czytaj więcej...

FAST I/O

W pewnych sytuacjach potrzebujemy szybszych funkcji wczytujących i wypisujących dane ze standardowego wejścia/wyjścia (klawiatura, monitor). Rozwiązując zadania, które są sprawdzane automatycznie przez serwer, przy dużej ilości danych wejściowych lub wyjściowych, możemy bardzo mocno podkręcić czas rozwiązania algorytmu. Do takich sprawdzarek zalicza się między innymi pl.spoj.com z bankiem kilkuset zadań tworzonych przez społeczeństwo tego serwisu a także serwis sprawdzający rozwiązania Olimpiady Informatycznej czy main.edu.pl. Niekiedy dzięki FAST I/O udaje się oszukać sprawdzarkę i rozwiązać zadanie nieoptymalnym algorytmem (oznacza to, że testy są nieprawidłowo dobrane lub nie da się fizycznie tak ich dobrać, aby szybkie wczytywanie/wypisywanie nie przechodziło).

Kluczem są szybkie funkcje wczytujące pojedynczy znak:

char c;
//wczytanie jednego znaku i zapisanie go w zmiennej c
c = getc_unlocked(stdin);
 
//lub
c = getchar_unlocked();
 

 

oraz wypisujące pojedynczy znak:

char c;
//wypisanie znaku przechowywanego w zmiennej c
putc_unlocked(c, stdout);
 
//lub
putchar_unlocked(c);
 

Powyższe funkcje zadeklarowane są w bibliotece {tex}cstdio{/tex} ale mogą być niezdefiniowane w niektórych kompilatorach, np. w Def C++.

register char c

Dodatkowo zmienną znakową można zadeklarować jako register co oznacza, że będzie ona wrzucona bezpośrednio do rejestru procesora (jeśli jest on wolny), co dodatkowo przyspieszy operacje na tej zmiennej (rejestry procesora są najszybszymi komórkami pamięci komputera).

register char c;

 

Funkcje typu inline

Pamiętajmy także, aby użyć funkcji typu inline, która jest opisana w tym miejscu.

Prześledźmy kilka przykładów:

Szybkie wypisywanie liczb całkowitych nieujemnych

Metoda tradycyjna:

#include<cstdio>
 
inline void putUI(unsigned int n) {
 
     if(n==0) //ten przypadek rozpatrujemy oddzielnie
     {
       putc_unlocked(48,stdout); //wypisz 0
       return; //zakończ wypisywanie
     }
 
   char tab[12];//tablica będzie przechowywać cyfry
     int p = 0;
     while(n != 0) { //wyłuskanie kolejnych cyfr z liczby n
        tab[p++] = (n % 10) + 48;
         n /= 10;
     }
     while(p--) 
         putc_unlocked(tab[p], stdout); //wypisanie liczby
}
 
int main()
{
  //wypisanie 344
  putUI(344);
 
  return 0;
}
 

 

Lub rekurencyjnie (ta funkcja działa poprawnie tylko dla liczb całkowitych dodatnich):

inline void putUI(unsigned int n) {
 
   if(n>0) { //wyłuskanie kolejnych cyfr z liczby n
         putUI(n/10);
         putc_unlocked(n%10+48,stdout);
     }
}
 

 

Szybkie wypisywanie liczb zmiennoprzecinkowych

inline void putDB(long double n)
{
  const int eps = 3; //ustalamy precyzjé
  long long k = (long long )(n*1000); //n*10^eps
   char arr[16],i;
     int p = 0;
    for(i=0;i<eps;i++) {
        arr[p++] = (k % 10) + 48;
        k /= 10;
    }
    arr[p++]='.';
    do{
      arr[p++]=(k%10)+48;
      k/=10;
    }while(k!=0); 
 
     while(p--) 
         putc_unlocked(arr[p], stdout);
}
 

 

Szybkie wczytywanie liczb nieujemnych

#include<cstdio>
 
inline void readUI(int *n) //tylko dodatnie
{
    register char c = 0;
    while (c < 33) c=getc_unlocked(stdin);
    (*n) = 0;
    while (c>32) {(*n)=(*n)*10LL + (c-48); c=getc_unlocked(stdin);}
}
 
int main()
{
  int a;
  readUI(&a);
 
  printf("%d",a);
 
  return 0;
}

 

Linię

Szybkie wczytywanie liczb całkowitych

inline void readINT(int *n) //ujemne i dodatnie
{
    register char c = 0, 
  znak_liczby=1;  //1 - liczba dodatnia, -1 - liczba ujemna
    while (c < 33) c=getc_unlocked(stdin);
 
    if(c==45) {znak_liczby=-1;  c=getc_unlocked(stdin);}//jesli napotkamy minus
    (*n) = 0;
 
  while (c>32) {(*n)=(*n)*10 + c-48; c=getc_unlocked(stdin);} 
 
    (*n)*=znak_liczby;
} 

 

Szybkie wczytywanie ciągów znaków

 inline int readS(char *a)//funkcja zwraca liczbę znaków
{
  int dl=0;
    register char c = 0;
    while (c < 33) c=getchar_unlocked(); 
     dl = 0; //zmienna będzie przechowywać liczbę znaków
    while (c>32) {
    a[dl++] = c; 
    c=getchar_unlocked();
  }
  a[dl]=0; //ustawienie końca ciągu znaków
  return dl; //zwrócenie liczby znaków
}

 

Nieokreślona liczba zestawów danych

Czasami dane wejściowe składają się z nieokreślonej liczby zestawów danych (np. w tym zadaniu). Zestaw tych danych kończy się specjalnym znakiem końca pliki EOF, który ma wartość {tex}-1{/tex}. W odpowiednim miejscu sprawdzamy warunek:

char c = getchar_unlocked();
 
if(c==-1)
{
  //zrób cos, bo nie ma juz co wczytywać
}
 

 

Jako ćwiczenie spróbuj zaimplementować:

  • wczytywanie nieokreślonej liczby zestawów danych
  • wczytywanie liczb zmienno-przecinkowych

Przydatne iformacje:
Kod ASCII znaku '0' = 48, znaku '-' = 45.

Białe znaki takie jak spacja, czy enter mają ASCII < 33.

Szyfrowanie trzech bitów

Zad. 2. W pliku szyfr.txt znajduje się zdanie, które jest zaszyfrowane według następującego schematu:

 

każdy znak, przedstawiony w formie binarnej szyfrujemy według szablonu:

 

trzy bity leżące po prawej stronie  są szyfrowane symetrycznie odpowiednio z trzema następnymi bitami, a następnie odwracane kolejnością. Dla przykładu zaszyfrujmy literkę "d ".

kod ASCII literki "d" to 100

100 = (01100100)2

Trzy bity na prawo (100), szyfrujemy z trzema następnymi bitami (100) (odpowiednio bit po bicie), według schematu:

  • gdy są takie same bity nadajemy wartość 0, w przeciwnym wypadku wartość 1
  • następnie te trzy bity zapisujemy w odwrotnej kolejności

Po zastosowaniu pierwszego podpunktu otrzymamy 01100000, zapis w odwrotnej kolejności nie ma znaczenia (trzy zera), czyli drugi podpunkt nie zmieni wartości tej liczby. Zaszyfrowany znak to " ' ".

 

a) zdeszyfruj tekst zawarty w pliku szyfr.txt

b) zaszyfruj następujący tekst:

Każdy program jest tylko na tyle dobry na ile jest przydatny!

Aby wyłuskać kod ASCII danego znaku należy użyć rzutowania typów.