Informacje dotyczące zadań maturalnych z informatyki 2015

Zakładam ten temat, gdyż przygotowuje się do matury z informatyki, która czeka mnie za rok :)
Często będę potrzebował Waszej pomocy, dlatego wolę założyć jeden temat, żeby nie zaśmiecać forum kolejnymi tematami typu "Problem z zadaniem z matury".
Mam nadzieję, że osoby które również będą podchodziły do tego egzaminu, również skorzystają z tego tematu, i będą mogli zajrzeć w moje rozwiązania oraz podzielić się efektami swojej pracy.

Oto moje rozwiązanie :

1. Podaj liczbę znaków U1, wczytaj do d.

2. i=2
   od bin[i] do bin[d] powtarzaj :
                            jeśli bin[i]=0 to wtedy bin[i]=1
                            w przeciwnym wypadku
                            bin[i]=0
   i=i+1

3.j=d 
  x=0
  liczba=1
  od bin[j] do bin[2] wykonuj :
                           jeśli bin[j]=1 to x=x+liczba
                           liczba=liczba*2
                           j=j-1

4.Jeśli bin[1]=1 to x=x*(-1)
5.Wyświetl x

Napisałem to w postaci listy kroków, nie wiem czy to jest do końca poprawny zapis. Chyba jednak będę pisał w języku programowania, żeby czegoś nie zapomnieć.
Czy wszystko się zgadza według Was? Coś byście zmienili, poprawili ?
Wydaje mi się, że tutaj wszystko jest ok.

Kolejne zadanie :

Rozwiązanie :

 
1. Podaj N>1

2. d=2
    i=1

3. Dopóki N>=d wykonuj :
                     jeżeli (N mod d)=0 to tab[i]=d
                     N=N div d
                     i=i+1
                     w przeciwnym wypadku d=d+1

4. i=1
   a=tab[i]
   b=1
   Dopóki tab[i]=tab[i+1]
             b=b+1
             i=i+1
   w przeciwnym wypadku wypisz a,b.

Całkiem mi się to pogmatwało, sprawdza czynniki, ale nie wiem jak sprawdzić ile jest elemetnów w tablicy (ile będzie czynników dla danej liczby), bo trzeba dać gdzieś licznik, aby przechodził po kolejnych liczbach.
Co tutaj trzeba zmienić ?

Będę bardzo wdzięczny za każdą pomoc i udział w temacie :)

Ad.1. Nie rozumiem po co negujesz wszystkie bity w tym twoim kroku numer 2. WTF? Poza tym nie rozumiesz jak działa kod uzupełnień do 1 bo to nie jest kod znak-liczba. Zaimplementuj ten swój algorytm i zobaczysz że nijak sie ma do zadania.
Ad.2. sensowniej byłoby użyć map<int,int> / unordered_map<int,int> albo w ogóle w tablicy tylko zliczać, tzn tablica[2] = liczba wystąpień czynnika 2. Opcja z tablicą jest o tyle ryzykowna że wymaga tablicy o rozmiarze największy_czynnik. Dlatego lepiej użyć mapy.

@Shalom, w U1 zamienia sie na przeciwne, robilem krok po kroku, teraz mi uswiadomiles, ze nie potrzebny jest ten krok 2. Wystarczy w 3 dac zeby dodawalo wartosc gdy wystapi 0 zamiast 1.

W jaki sposób mogę zliczać w tablicy?

Co do pierwszego wyszło mi coś takiego:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int d = 0;
    char temp;
    int wynik = 0;
    vector<int> tab;
    
    cin >> d;

    for(int i = 0; i < d; i++)
    {
        cin >> temp;

        tab.push_back(temp - '0');
    }

    for(int i = tab.size() - 1; i >= 0; i--)
    {
        if(tab[i] == 1)
        {
            tab[i] = pow(2, tab.size() - i - 1);

            if(i != 0)
            {
                wynik += tab[i];
            }
        }
        else
        {
            tab[i] = 0;
        }
    }

    if(tab[0] != 0)
    {
        tab[0] *= -1;
        tab[0]++;

        wynik += tab[0];
    }

    cout << wynik;

    return 0;
}

W jaki sposób mogę zliczać w tablicy?

Nie rozumiem pytania. Całe zadanie sprowadza sie do kodu (potrzeba tylko jedną trywialną funkcję napisać):

map<int,int> counting;
int lastFactor = 1;
while(number>1){
  lastFactor = findNextFactor(number, lastFactor);
  counting[lastFactor] = counting[lastFactor]+1;
  number/=lastFactor;
}

i voila, masz teraz mapę która przechowuje pary liczba->wystąpienia. Wystarczy tą mapę wypisać i już.

@Bartolinho10

Ale po co chcesz negować bity do obliczania?

Jak masz liczbę zapisaną w systemie Z1 to waga najbardziej znaczącego bitu wynosi , gdzie to ilość bitów użytych do zapisania liczby. Pozostałe bity tak jak w zwykłym zapisie dwójkowym.

@Degusto, @Bartolinho10, co do pierwszego powinno wyjść tyle:

int U1ToInt(const char *U1)
  {
   int ret=0;
   for(const char *i=U1+1;*i;++i) ret=(ret<<1)+*i-'0';
   if(*U1=='1') ret=-(~ret);
   return ret;
  }

ewentualnie jeszcze wczytywanie napisu.
http://ideone.com/Hxwjp7

@_13th_Dragon

No chyba nie do końca, bo np. 1111 w systemie U1 to jest 0, a nie -7.

@123456, no tak trochę mi się zapomniał ten U1, w takim razie jeszcze prościej:

int U1ToInt(const char *U1)
  {
   int ret=0,inv=(*U1=='1');
   while(*(++U1)) ret=(ret<<1)+((*U1-'0')^inv);
   return inv?-ret:ret;
  }

http://ideone.com/tvPriz

@_13th_Dragon

Ale to ciągle daje złe wyniki :P

110 powinno dać -1 a daje 1.
10000010 powinno dać -125 a daje 125.

Poprawiłem, powinno być ok.

 
1. Podaj liczbę znaków U1, wczytaj do d.

2. j=d
   x=0
   liczba=1

   Jeśli bin[1]=0 to wykonuj :
                          od bin[j] do bin[2] wykonuj:
                                                   jeśli bin[j]=1 to x=x+liczba
                                                   liczba=liczba*2
                                                   j=j-1                      

   Jeśli bin[1]=1 to wykonuj :
                          od bin[j] do bin[2] wykonuj :
                                                   jeśli bin[j]=0 to x=x+liczba
                                                   liczba=liczba*2
                                                   j=j-1

3. Jeśli bin[1]=1 to x=x*(-1)
4.Wyświetl x

Kolejne zadanko, wydaje mi się poprawne, proszę o ocenę. Robione szybko, bez większego zastanawiania, bo zaczynam próbować ogarniać się szybciej czasowo, żeby potem czasu nie zbrakło :)

Rozwiązanie :

1.

   max=0;
   i=0; 
   tab[100];
 
2.

powtarzaj
   jeśli n mod 2=1 to
      max=max+1;
      tab[i]=max;
   w przeciwnym wypadku i=i+1;
      n=n div 2;
aż n=0; 

3.
   m=0;
   j=0;

   powtarzaj 
      jeśli tab[j]>m to m=tab[j];
      j=j+1;
   dopóki j<=i;
 
4.

wyświetl m (maksymalna liczba jedynek obok siebie)

W jaki sposób w języku C mogę rozdzielić napis na litery, czytając z plików? np. żeby później zmienić je na kod ASCII.
Próbowałem pobierać całe linie funkcją fgets. Jednak nie wiem co później zrobić, znalazłem funkcję strlen, która sprawdza długość linii, np. w tablicy, jednak nie za bardzo mi to działa..
Czy pobrać do zwykłej tablicy jakoś po literze?

Podpowiecie, w jaki sposób to zrobić najlepiej?

Najlepiej to czytać całymi liniami z pliku - będzie dużo szybciej; Do konkretnych znaków łańcucha można się przecież bez problemu odwoływać - zerknij no do jakiegoś kursu, bo trochę Ci fundamentalnej wiedzy brakuje.

Okej,
@furious programming, pobieram fgets do tablicy np. 20 elementowej char, to jest każda litera w oddzielnej z tego co doczytałem, więc np. wywołując tablice[0] to powinna być pierwsza litera ? Próbowałem zrobić tak, aby pobierać po kolei kod ascii każdej litery, a pętle określiłem jako strlen(tablica).

Zależy jak masz indeksowaną tę tablicę; Ogólnie to nie programuję w C, więc funkcji Ci nie doradzę; Jednak zasada jest taka sama, przynajmniej w tych najpopularniejszych językach;

Gdybym sam miał takie coś zrobić, to skorzystałbym z łańcuchów o (teoretycznie) dowolnej długości, a nie z tablic; Dlatego że nie można z góry założyć, że każda linia w pliku ma co najwyżej 20 znaków; Czyli coś w tym stylu:

var
  txtInput: TextFile;
  strLine: AnsiString;
begin
  AssignFile(txtInput, 'C:\Foo.txt');
  Reset(txtInput);
  try
    while not EoF(txtInput) do
    begin
      ReadLn(txtInput, strLine);
      { ... }
    end;
  finally
    CloseFile(txtInput);
  end;
end.

Oczywiście to tylko przykład - być może zrobiłbym to nieco inaczej, ale i tak linie z pliku ładowane były by do łańcuchów (o listach nie ma co wspominać).

Dziś robiłem zadanie z poziomu rozszerzonego, i coraz lepiej mi idzie. Fakt, że spędziłem nad tym ok. 1h, jednak ważne, że coś mi wyszło, mam nadzieję, że wejdzie mi w nawyk i takie rzeczy będę robił max. 30 minut :)

Oto zadanie :

KOD :

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

int bin_dec(int binar)
{
	int cyfra=0;
	int bin=binar;
	
	int dec=0;
	int p=1;
	
	do 
	{
		cyfra=(bin%10);
		bin=bin-cyfra;
		bin=bin/10;
		dec=dec+p*cyfra;
		p=p*2;
	}
	while(bin>0);
	
	return dec;
}

int main(int argc, char *argv[]) 
{
	FILE *plik;
	int i=0;
	int bin=0;
	int dec=0;
	
	int P_2=0;
	int P_3=0;
	int P_5=0;
	
	plik=fopen("C:\\liczby1.txt","r");
	
	for(i=1;i<=1000;i++)
	{
		fscanf(plik,"%d",&bin);
		dec=bin_dec(bin);
		
		if(dec%2==0) P_2++;
		if(dec%3==0) P_3++;
		if(dec%5==0) P_5++;
	} 
	
	fclose(plik);
	
	plik=fopen("C:\\podzielnosc.txt","a");
	fprintf(plik,"%d \n",P_2);
	fprintf(plik,"%d \n",P_3);
	fprintf(plik,"%d \n",P_5);
	
	fclose(plik);
	
	return 0;
}

Niestety, coś źle mi wychodzi. Z pierwszym plikiem problemów nie ma, wychodzi mi tak jak w przykładowym rozwiązaniu, w liczby2.txt, oraz liczby3.txt po dwie liczby są niezgodne.
Pewności, co do wiarygodności tych "właściwych odpowiedzi" nie mam, ale wydaje mi się to bardzo prawdopodobne...

Jak mówi zadanie, w liczby1.txt max. długość liczby to 12, w liczby2 - 30 znaków, a w liczby3.txt - 200 znaków (czyli potrzeba ok. 25 bajtów, jak dobrze licze)..
Błędów żadnych przy kompilacji nie ma, więc możliwe, że chodzi tutaj o zbyt małą zmienną, skoro używałem int?
Jeśli tak, to w jaki sposób mogę zarezerwować większą zmienną? Próbowałem z long int, ale to nie zmieniło nic..

W załączniku wstawiam pliki, moje rozwiązanie, oraz właściwe odpowiedzi.
Proszę o porady, jeśli coś jest źlę, proszę też o krytykę, postaram się zniwelować błędy, aby było lepiej :)

Nie ma opcja żeby tak duża liczba binarna zmieściła się w jakimś wbudowanym typie liczb całkowitych, nie potrzebnie stosujesz konwersje na system dziesiętny, pozostań na systemie binarnym.

@Bartolinho10 nic w tym kodzie nie jest dobrze. W ogóle nie zrozumiałeś zadania ani jego intencji. To co napisałeś jest bez sensu. Przecież tam nie masz żadnego algorytmu ani nic. Powinna ci sie zapalić chyba lampka że coś jest nie tak...
W tym zadaniu należy MYŚLEĆ.
Liczba binarna jest podzielna przez 2 (parzysta!) jeśli ostatni bit jest 0. Nic więcej...
Podzielność przez inne liczby jest już bardziej skomplikowana, ale też jest znana.
http://www.matematyka.pl/128458.htm
http://www.matematyka.pl/30729.htm

@Shalom, jeśli chodzi o cały szkielet, to chyba nie jest tak źle, bo przykład znalazłem w C++ i jest prawie tak samo, jednak nie ma tej konwersji z Bin na Dec. Faktycznie może to był błąd, jednak to jako pierwsze przyszło mi do głowy, poza tym połowę zadań wykonało :) Zastosować tutaj tablicę, dla poszczególnych znaków liczby binarnej i na tym działać?

Innej rady nie ma.
Jaki znów szkielet? o_O WTF? To masz maina, dwie pętle i czytanie z pliku. Co za szkielet to niby jest? To są takie podstawy że powinieneś sobie taki "szkielet" napisać w minutę, obudzony w środku nocy.

@Bartolinho10 Tak, działaj na tablicy intów, gdzie trzymasz poszczególne cyfry.

Natomiast nie uważam tak jak @Shalom, że pierwotne rozwiązanie było bez sensu, ...nie ma żadnego algorytmu. Dla małych liczb to jakoś działa, owszem autor nie załapał, że jak liczby mają 200 cyfr binarnych to nie da rady zapisać we wbudowanym typie, ale dla każdego co innego jest oczywiste. I chwała mu, że idzie pytać z jakimś kodem, a nie czeka na gotowca.

Zmieniłem trochę swój kod, wyrzuciłem konwersję z binarnego na dziesiętny, spróbowałem operować na stringach.
Niestety, wynik wychodzi zły, tym razem w tysiącach. Nie wiem gdzie jest błąd, próbowałem zamieniać pętle, warunki, nic sam więcej nie wymyśliłem. Co o tym myślicie?
@Shalom próbowałem zastosować zliczanie jedynek i porównywanie, tak jak doradzałeś.

 while(feof(plik)==0)
	{
		fgets(tab,200,plik);
		Last=strlen(tab);
		if(tab[Last]==0) P_2++;
		
		for(i=0;i<strlen(tab);i+=2)
			{        
			if(tab[i]==1) N_parz+=tab[i];
   		 if(tab[i+1]==1) Parz+=tab[i+1];
			roznica=Parz-N_parz;
			
			if(roznica%3==0) P_3++;
			if(roznica%5==0) P_5++;
			}
		
	} 

Co tutaj jest źle? Proszę o wyrozumiałość.

Wczytałeś z wejścia stringa czyli ciąg ZNAKÓW a porównujesz to potem z liczbami. Widzisz tu pewien problem? Z wejścia wczytałeś na przykład char o wartości '1' a następnie porównujesz go z liczbą 1. To nie jest to samo...

roznica=Parz-N_parz;
if(roznica%3==0) P_3++;
if(roznica%5==0) P_5++;

Dlaczego to jest w pętli for? Przecież masz to liczyć raz dla każdej liczby, a nie cyfry.

fgets(tab, 200, plik);

Ta funkcja wczytuje do tablicy tab 200199 znaków, przy czym znak 0 zapisany jako char ma wartość 48, 1 ma wartość 49 itd. Czyli zamiast:

if (tab[i] == 1)

trzeba

if (tab[i] == '1')    // to jest równowazne  if (tab[i] == 49)

Ogólnie naucz się debugować, bo bez tego ciężko się programuje.
Sposób prostszy: wypisz zmienne w ważnych punktach i potem zobacz czy mają wartość jak powinny. Na przykład:

roznica = Parz-N_parz;
printf("Parz: %d N_parz: %d Roznica: %d\n", Parz, N_parz, roznica);

Dzięki temu możesz śledzić gdzie program zaczyna się zachowywać inaczej niż planowałeś.
Sposób wygodniejszy: używaj debuggera, nie musisz dużo tam robić, wystarczy wykonywać program krok po kroku i mieć listę wszystkich zmiennych z wartościami.

Dopiero teraz wyzerowałem, ogarnąłem trochę kod. Wynik nr. 2 czyli podzielność prze 3 wychodzi już dobry :) Tylko jeszcze nie ma pewności,że nie z przypadku.
Dziwi mnie fakt, sprawdzania podzielności przez 2.

Sprawdzam ostatni element, wyświetliłem sobie go i wyszło mi za każdym razem 11 (ostatnia cyfra binarnej jest 10), zmieniłem sobie na strlen(tab)-1, wtedy faktycznie wychodzi 10, ale nic to mi nie zmieniło.. Ciągle wychodzi w wyniku 0. Myślę dalej.

 
while(feof(plik)==0)
	{
		fgets(tab,200,plik);
		Last=strlen(tab)-1;
		if(tab[Last]=='0') P_2++;
		
		for(i=0;i<strlen(tab);i+=2)
			{        
			if(tab[i]=='1') N_parz+=tab[i];
   			if(tab[i+1]=='1') Parz+=tab[i+1];
			}
			
	roznica=Parz-N_parz;
	//printf("nieparz- %d parz-%d  roznica- %d last - %d \n",N_parz,Parz,roznica,Last);
	if(roznica%3==0) P_3++;
	if(roznica%5==0) P_5++;
	N_parz=0;
	Parz=0;	
	} 

http://pl.wikibooks.org/wiki/C/fgets

Czytanie przerywa, gdy przeczyta size - 1 znaków, natrafi na koniec pliku lub znak końca linii (znak ten jest zapisywany do str). Na końcu fgets() dopisuje znak '\0'.

W szczególności jeśli chcesz wczytać liczbę 200-cyfrową, to jako argument fgets() powinno być 201.

if(tab[i]=='1') N_parz+=tab[i];

Za każdym razem zwiększasz N_parz o 49.

zamiana znacznika `` na <quote> - furious programming

Zrobiłem to inaczej, wyniki dla 2 oraz 3 są poprawne. Zamiast czytać linie dopóki błędu nie zwróci feof() , lecę licznikiem do 1000, bo z góry miałem określone ile jest linii. Pozostała mi teraz tylko podzielność przez 5, tutaj myślę, że cały algorytm sumowania parzystych i nieparzystych jest coś nie tak dla 5. Co o tym myśli @Shalom ?

 
int linie=0;
while(linie<1000)
	{
		fgets(tab,200,plik);
		Last=strlen(tab)-2;
		if(tab[Last]=='0') P_2++;
		
		for(i=0;i<strlen(tab);i+=2)
			{        
			if(tab[i]=='1') N_parz+=tab[i];
   			if(tab[i+1]=='1') Parz+=tab[i+1];
			}
			
roznica=Parz-N_parz;
printf("nieparz- %d parz-%d  roznica- %d last - %c \n",N_parz,Parz,roznica,tab[Last]);
if(roznica%3==0) P_3++;
if(roznica%5==0) P_5++;
N_parz=0;
Parz=0;	
	
linie++;
	} 

Algorytm podzielności przez 5 jest inny niż algorytm podzielności przez 3, przeczytaj jeszcze raz dokładnie.

Cecha podzielności przez 5 wygląda tak: dzielimy liczbę b na grupy dwucyfrowe począwszy od prawej (ewentualnie uzupełniając o zero na początku), a następnie (również począwszy od prawej) na zmianę dodajemy i odejmujemy tak powstałe liczby. Otrzymana w wyniku liczba daje taką samą resztę z dzielenia przez 5, jak liczba wyjściowa.

Czyli mając np. liczbę 1100110 będzie (0+1)-(1+0)-(0+1)-(1) ?