Matura 2019 – zadanie 4 – potęgi, silnia i NWD

Na moim kanale U źródeł programowania rozpocząłem miniserię poświęconą zadaniu 4 z matury 2019.
Na razie są odcinki:

• 4.1 wyjaśnienie i implementacja w Javie
  

• 4.1 tłumaczenie na język C++
  

• 4.1 wyjaśnienie i implementacja w Javie
  

Kolejne w drodze, ale proszę już o jakieś opinie, wskazówki, jeżeli można to code review. Co można zrobić lepiej, a co jest super?

Odnoszę się tylko do kodu C++. Myślałem że będzie bardziej, ahem, przedpotopowo, ale ogółem jest dobrze - szczególnie jeśli mówimy o poziomie matury.

Jedyny gruby błąd merytoryczny:
15:17 - C++ nie ma "tablicy o zmiennej długości"
Nit-picki:

• using namespace std (to bym uznał za gruby błąd w produkcyjnym kodzie, ale to matura ;​) - ale koniecznie trzeba wspomnieć o tym imo)
• brak uzasadnienia użycia tablicy zamiast (wydawałoby się) bardziej naturalnej struktury dla tego rodzaju problemu (np. set albo hashset) - czy to było poruszone w części o javie? Jeśli tak to chociaż wzmianka by się przydała
• użycie endl - endl wymusza flush bufora, normalną praktyką jest wypisywanie \n bezpośrednio (głupie? tak, ale cóż...)
• polskie znaki w kodzie - kompletnie zbędne imo, szczególnie jak nie działają
• jest jakiś powód dla którego używasz emplace_back zamiast push_back? Jak dla mnie to zbędne się wydaje
• teoretycznie tabelkę do wyszukiwania można wyliczyć w czasie kompilacji (albo zahardkodować)

Ale ogółem treść jest ok.

W kwestii maturalnej, widać teraz przewagę Pythona - to co zajęło z 30 linijek, mi zajęło trzy:

import sys
pot3 = {3**k for k in range(50)}
print(sum(int(x) in pot3 for x in sys.stdin.readlines()))

Oczywiście, w kodzie produkcyjnym nigdy bym czegoś takiego nie ujął, ale matura to jest wyścig z czasem, szczególnie jak chce się osiągnąć wysokie wyniki (gdy ja pisałem maturę, był ostatni chyba rok bez Pythona, i byłem zmuszony wtedy do C++, m.in. dlatego właśnie straciłem większość punktów które straciłem).

Edit, podobnie zadanie drugie:

import sys, math
print(*[x for x in map(int, sys.stdin.readlines()) if x == sum(math.factorial(int(d)) for d in str(x))], sep='\n')

Dorzuciłem zadanie 4.3 w Javie:

Z ciekawości zrobiłem dwie alternatywne (krótsze) wersje w C++:

1. C z klasami (test.cpp)

#include <iostream>
int pot3[100001],sum;
main() { 
	int x; 
	for(int i = 11, a = 1; i; i--, a *= 3) pot3[a] = 1;   
	while(std::cin >> x) sum += pot3[x];
	std::cout << sum << std::endl;	
}	

1. bardziej C++11 (test2.cpp)

#include <iostream>
#include <unordered_set>
main() { 
	std::unordered_set<int> pot3;
	int x, sum = 0; 
	for(int i = 11, a = 1; i; i--, a *= 3) pot3.insert(a);   	
	while(std::cin >> x) sum += pot3.count(x);
	std::cout << sum << std::endl;	
}	

Wynik testów (wersja pajtonowa z https://4programmers.net/Forum/1682688):

python -m compileall . && time python test.pyc <liczby.txt
Listing . ...
Compiling ./test.py ...
18

real	0m0,014s
user	0m0,009s
sys	0m0,004s
piotr@piotr-Prec-M47:~/progs/cpp/tests/matura2019$ g++ test.cpp && time ./a.out <liczby.txt
18

real	0m0,002s
user	0m0,002s
sys	0m0,000s
piotr@piotr-Prec-M47:~/progs/cpp/tests/matura2019$ g++ test2.cpp && time ./a.out <liczby.txt
18

real	0m0,002s
user	0m0,002s
sys	0m0,000s

vpiotr napisał(a):

Kopiuj

int pot3[100001],sum;
	for(int i = 11, a = 1; i; i--, a *= 3) pot3[a] = 1;   

Ciekawe podejście, tylko widzę dwa ale.

Ale 1) Czy ten zapis pętli można uznać za maturalny? Nie spotkałem się z nim w żadnym z podręczników ani szkolnych ani do nauki programowania.

Ale 2) I drugie większe ale – twój algorytm wpierdziela pamięć jak stonka ziemniaki. Bo mamy sto tysięcy plus jeden intów zajętych. Int ma typowo 4 bajty, czyli żegnamy się z 400 001 bajtów. A jeżeli liczby będą miały większy zakres? O 1 zero i zamiast 100 000 będą miały 1 000 000 to zjesz 3,8MiB pamięci. Na Pececie pewnie przejdzie, ale na takim Arduino pewnie średnio. Choć i na pececie chyba tak duża zmienna nie może być jako statyczna, nie?

Ja jestem starszym człowiekiem i pamiętam jak miałem 2MiB RAM i błyszczałem, bo kumple mieli 1MiB (na 286, a ja miałem 386) i trochę zawsze mam awersję do takich metod.

400kB w dzisiejszych czasach to tyle co nic, nawet warte kilka dolarów raspberry π 0 ma 512MB ramu. Ba, przecież w nowszych prockach cała ta tabelka wejdzie do L2 ;​)

Jeśli piszesz w jakimś ograniczonym środowisku to zwracasz na inne rzeczy uwagę, ale tutaj @vpiotr po prostu pokazał przykład z wyszukiwaniem o złożoności O(1).

Ad. 1) O ile mi wiadomo zapis tej pętli jest jak najbardziej OK.

Ad. 2) W sumie argument nie na miejscu, ale jestem starszym człowiekiem i pamiętam jak pisałem w C przy 48 kB RAM... (Elwro Junior, HiSoft C).
Tylko co to zmienia skoro obecnie cała ta tablica zmieści się w cache L3?

Niby się zgodzę, że nieco rozrzutnie, ale mój PC dał sobie radę jak taka globalna tablica miała 4 GB, więc co tu mówić o jakichś kulkuset KB. Z kolei, dało się prosto nieco zbić wymagania przez użycie std::vector<bool> (tutaj 32-krotnie).

enedil napisał(a):

Niby się zgodzę, że nieco rozrzutnie, ale mój PC dał sobie radę jak taka globalna tablica miała 4 GB, więc co tu mówić o jakichś kulkuset KB. Z kolei, dało się prosto nieco zbić wymagania przez użycie std::vector<bool> (tutaj 32-krotnie).

Na czym kompilowałeś? Jeśli na g++ to limit jest 2 GB, ale można to obejść:

#include <iostream>
using namespace std;

int tab[2L*1024*1024*1024];
int main() 
{    
    long last = sizeof(tab)/sizeof(*tab)-1;
    cout << "Size of int: " << sizeof(int) << " bytes" << endl;
    cout << "Size of tab: " << sizeof(tab) << " bytes" << endl;
    tab[0] = 5;
    tab[last] = 11;
    int a = tab[0] + tab[1024] + tab[last];
    cout << "sum: " << a << "\n";

    return 0;
}

Wynik z limitem:

piotr@piotr-Prec-M47:~/progs/cpp/tests/matura2019$ g++ size.cpp
/tmp/ccHtaY4g.o: In function `__static_initialization_and_destruction_0(int, int)':
size.cpp:(.text+0x144): relocation truncated to fit: R_X86_64_PC32 against `.bss'
size.cpp:(.text+0x157): relocation truncated to fit: R_X86_64_PC32 against `.bss'
collect2: error: ld returned 1 exit status

Wynik bez limitu:

piotr@piotr-Prec-M47:~/progs/cpp/tests/matura2019$ g++ -mcmodel=large size.cpp
piotr@piotr-Prec-M47:~/progs/cpp/tests/matura2019$ ./a.out 
Size of int: 4 bytes
Size of tab: 8589934592 bytes
sum: 16

Jeszcze większa tablica:

piotr@piotr-Prec-M47:~/progs/cpp/tests/matura2019$ g++ -mcmodel=large size.cpp
piotr@piotr-Prec-M47:~/progs/cpp/tests/matura2019$ ./a.out 
Size of int: 4 bytes
Size of tab: 17179869184 bytes
sum: 16

Może chodziło o zmienną stosową?

Wersja bez tej strasznej pętli for i alokacji, za to z nutką JavaScriptu:

#include <iostream>
int main() { 
    int x, sum = 0; 
    while(std::cin >> x) {
		while(x && (x % 3 == 0)) x /= 3;
		sum += (x == !!x);
	}	
    std::cout << sum << std::endl;  
}

Działa nawet jeśli mamy 256 bajtów RAM...

U mnie dla podanego pliku tak samo szybkie jak poprzednie wersje ode mnie.

Widząc odpowiedź @vpiotr aż samemu nabrałem ochoty aby zmierzyć się z tym zadaniem :)

#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdint>

int main() {
	std::cout << std::count_if(std::istream_iterator<int32_t>(std::cin),
							   std::istream_iterator<int32_t>(),
							   [](auto x) {
							     return x > 0 && 1162261467 % x == 0;
							   });
}

lub bez MAGIC_NUMBER:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <limits>
#include <cmath>
#include <cstdint>

int main() {
    std::cout << std::count_if(std::istream_iterator<int32_t>(std::cin),
                               std::istream_iterator<int32_t>(),
                               [](auto x) {
                               	 static decltype(x) maxPowOfThreeLog = std::log(std::numeric_limits<decltype(x)>::max()) / std::log(3); 
                               	 static decltype(x) maxPowOfThree = std::pow(3, maxPowOfThreeLog);
                                 return x > 0 && maxPowOfThree % x == 0;
                               });
}

Efekty dźwiękowe dla "subscribe" były dla mnie bolesne. Mimo, że twój głos miałem raczej cicho, to te efekty dźwiękowe były na tyle głośne, że poczułem spory dyskomfort słysząc to w słuchawkach.
Są po prostu z głośne w stosunku do twojego głosu.