FR_17_10 - Naiwny szyfr

[mr_boowa]

SPOJ.com - Problem FR_17_10

Witam,
napisałem rozwiązanie w C i sędzia zgłasza “Błędna odpowiedź”, natomiast kod w python przechodzi. Ktoś mi może powiedzieć co jest nie tak w kodzie C?

Z góry dziękuje.

[hipcia]

decrypted[j] = 0;
printf("%s\n",decrypted);

[m_labanowicz]

Czesc,

Taki aspekt techniczny:

Tworzenie dużych tablic na STACK’u nie jest zalecane, należy zawsze przyjąć, że STACK jest nieduży.
Inaczej można doświadczyć dziwnych efektów, gdzie wywalenie się programu jest najmniejszym problemem.

Każda zmienna/tablica/struktura zdefiniowana w funkcji umieszczana jest na stacku:

int main() {
    char buff[1000005];
    char decrypted[1000005];

Do dużych zmiennych najlepiej uzywac HEAP’a (czyli malloc + free), ale jeżeli juz nie chcemy sie w to bawić, to
należy wstawic takie tablice do BSS’a (na dzien dobry te tablice będą wtedy wyzerowane), można to zrobić na dwa sposoby:

a) używajac słowa kluczowego static:

int main() {
    static char buff[1000005];
    static char decrypted[1000005];

b) deklaracja poza funkcja:

char buff[1000005];
char decrypted[1000005];

int main() {

Pzdr.

[narbej]

Moim skromnym zdaniem, twój @m_labanowicz, aspekt techniczny jest nietrafiony. Chociaż jest poprawny, tak się wydaje, to zupełnie nie wyjaśnia problemu pytającego.
A wyjaśnienie jest takie, ze funkcją printf ("%s\n", ... w c drukujemy c-string. W c, string jest tablicą char, zakończona \0, którego [\0] zabrakło w twoim programie. W pythonie string jest zapisany jako tablica char i nie jest zakończona \0.

Niedocenione? rozwiązanie problemu, jakie podał @hipcia, jest [znowu moim skromnym zdaniem], sorry, lepsze od twojego @m_labanowicz .
Co myślę o zmiennych globalnych, każdy kto mnie zna wie?
Static zostało wymyślone aby zachować zawartość tablicy przy kolejnych wywołaniach funkcji. Funkcje main wywołujem raczej tylko raz, a użycie zlecenia static do wyzerowania całej tablicy jest nadmiarowe. Obie tablic,mogą zawierać dowolne śmieci, bo są nadpisywane nowymi wartościami, a funkcja scanf ("%s"…) dodatkowo dopisuje na końcu zero.

Przykład użycia static, ze strony https://stackoverflow.com/questions/572547/what-does-static-mean-in-c, ale można znaleźć dowolne inne źródło w necie lub książkach:

#include <stdio.h>

void foo()
{
    int a = 10;
    static int sa = 10;

    a += 5;
    sa += 5;

    printf("a = %d, sa = %d\n", a, sa);
}


int main()
{
    int i;

    for (i = 0; i < 10; ++i)
        foo();
}

Kilka rozwiązań problemu w c, czy wszystkie są poprawne?:

1. sposób @hipcia

2. decrypted [1000005] = {} <-- nadmiarowe wyzerowanie całej tablicy

3. Zmiana kolejności deklaracji tablic - najpierw decrypted, potem buffor – w tym zadaniu to zadziałało.

4. znamy wyjściową kolejność, więć zamiast do tablicy decrypted, możemy wypisywać od razu do stdout [do bufora stdout]

5. metoda @m_labanowicz static decrypted tylko to jedną tablicę

6. tylko tablica decrypted globalna - by @m_labanowicz

@mr_boowa – twoje rozwiązania są dobre, więc powinieneś wyedytować swój post i skasować oba linki do ideone.

------------------

NA KONIEC

ZDROWYCH I WESOŁYCH ŚWIĄT

[narbej]

należy zawsze przyjąć, że STACK jest nieduży.

Czy nie dotyczy to programów typu: https://ideone.com/h2V9E7

Dla pewnych małych wartości n, programy działają, ale dla wiekszych już się wysypują.

Gdy zadeklarujemy większą wartość n - znaną w momencie kompilacji - możemy deklarować dużo większe zmienne lokalne, a kompilator odpowiednio sporo powiększy STACK. Twoim sposobem, można deklarować większe tablice, ale , ale każda pamięć nie jest z gumy i ma swoje ograniczenie wielkości.

[m_labanowicz]

Czesc,

Moj aspekt techniczny odnosił się tylko do tego, aby nie tworzyć dużych zmiennych na STACK’u.

Przepełnienie STACK’a (stackoverflow), jest bardzo niebezpieczne,
po prostu dobrze o tym wiedzieć.

Aby uniknąć tego problemu podałem możliwe podejścia, gdzie static jest akceptowalnym rozwiązaniem.

Ostatnio oglądałem na Youtubie gościa, który krytykował kurs Pana Mirosława Zelenta, i ten ów krytyk zwracał uwagę, że to jest źle, że tablice, których rozmiary były ogromne (32MB), są definiowane globalnie, lepiej jakby były lokalnie, bo kod byłby czytelniejszy.
Oczywiście, może i kod byłby czytelniejszy, tylko że nie zawsze by zadziałał :).
Należy na to po prostu uważać i przyjąć, że STACK jest mały.
W tym akurat wątku Pan Zelent nie popełnił błędu, brakowało jedynie wytłumaczenia, dlaczego definicja tablicy jest globalna.

PS: Nawet nie wiedziałem, że wystarczy mieć wyzerowaną tablicę, aby ten program oryginalny zadziałał :).

Jeżeli chodzi o nadmiarowe zerowanie tablic, to w obecnych systemach (przykładowo linux), obszar, który ma być wyzerowany, może być wyzerowany przez system dopiero w momencie pierwszego dostępu do danej strony pamięci.

Generlanie najlepszym sposobem na duże dane jest używanie HEAP’a.
W C++ tak własnie działa std::vector lub std::string.

Pzdr.

[narbej]

Ostatnio oglądałem na Youtubie gościa, który krytykował kurs pana xxxxxxxxxxxxx, i ten ów krytyk zwracał uwagę, że to jest źle, że tablice, których rozmiary były ogromne (32MB), są definiowane globalnie, lepiej jakby były lokalnie, bo kod byłby czytelniejszy.

1. Pewnie krytykujący miał dużo racji.
2. To programista [koder] pisze kod i czasami wie co robi i na jakie niebezpieczeństwa się naraża i ma [czasami ] różne inne, dodatkowe priorytety oprócz AC [na spoju]. Ma czasami takie fanaberie, narażając się świadomie lub nieświadomie na SO i inne takie, aby kod był nie tylko dodatkowo ładny i jeszcze, żeby oprócz AC był najszybszy jak to tylko jest możliwe, nie zważając na groźbę SO.
3. Czy tablica 32 MB jest ogromna? Na pewno w systemie embadded na arduino lub sterowniku pralki na mikrokontrolerze, tak jest. Nie powinno się więc generalizować i uogólniać, lecz dostosowywać do aktualnej sytuacji i analizować!
4. Proszę, potestuj: https://ideone.com/J86cRS, a potem : https://ideone.com/0tw9ch i sam spróbuj wyciągnąć wnioski i zastanów się, czy chodzi tu tylko, a właściwie czy w ogóle chodzi tutaj o piękno kodu!? A może o zupełnie coś innego? No i czy zastosowana tu tablice jest już wystarczająco ogromna, czy jeszcze nie?

W tym akurat wątku Pan xxxxx nie popełnił błędu, brakowało jedynie wytłumaczenia, dlaczego definicja tablicy jest globalna.

Może i racja, może tu w tym miejscu wyjątkowo nie popełnił błędu?, chociaż w to szczerze wątpięale … Dużo dużo tam brakowało. Już tyle złego napisałem na temat tego kursu, i jego błędach więc może tym razem napiszę kilka dobrych rzeczy.? Będzie to bardzo trudne.

1. Fajnie, że jest i że tak łatwo na niego trafić, bo inne kursy, nawet może i są jakieś lepsze ale albo ciężko je znaleźć albo są w przeciwieństwie do rzeczonego płatne.

2. Fajnie, że zawiera zawiera tyle błędów i że autor, pan xxxxx ich nie poprawia. Podobno fajniej jest uczyć się na cudzych błędach, tylko czy dotyczy to także początkujących adeptów programowania, którzy mogą nie dostrzec tych oczywistych, a co dopiero głębiej ukrytych błędów i niedociągnięć?

3. Super, że można oglądać i słuchać. Przy książce też można zasnąć, ale nie jest to takie komfortowe.

4. …

5. może kiedyś dopiszę, chociaż ciężko mi znaleźć więcej zelet

6. …

7. A tak na serio, jeżeli to przeczytałeś, to domyślasz się, jaki mam stosunek do tego kursu. Jeżeli więc świadomie nie chcesz mi się narazić, nie wspominaj ani tego kursu ani jego autora!! A uchowaj Cię, nie chwal się, że skorzystałeś, zachowaj lepiej to dla siebie.

PS: Nawet nie wiedziałem, że wystarczy mieć wyzerowaną tablicę, aby ten program oryginalny zadziałał :).

No nie wiem, wystarczy przecież tylko przeczytać podpowiedź @hipcia i zorientować się, co można zrobić, aby oryginalny program zadziałał, czyż nie? I przecież z tej podpowiedzi jasno chyba wynika, że nie trzeba mieć wyzerowanej tablicy!?, a tylko dodać jedno jedyne zero [null], w odpowiednim miejscu, tak, aby funkcja printf zadziałała poprawnie!

Więc jeszcze raz.

Jak działa funkcja printf w języku C?
np cytat z: https://pl.wikibooks.org/wiki/C/Napisy

Kluczowy jest … kończący napis znak null. W zasadzie wszystkie funkcje operujące na napisach opierają właśnie na nim. Na przykład, strlen szuka rozmiaru napisu idąc od początku i zliczając znaki, aż nie natrafi na znak o kodzie zero. Jeśli nasz napis nie kończy się znakiem null, funkcja będzie szła dalej po pamięci.

PS
A niebezpieczeństwa czychające na nieświadomego (początkującego) programistę C, to nie tylko So (stack overflow), ale np przepełnienie bufora. Lekarstwo? Wiedza i świadomość. Przesiadka na C++.

[m_labanowicz]

No kurka wodna, muszę napisać, że się kompletnie z tym nie zgadzam:

Czy tablica 32 MB jest ogromna? Na pewno w systemie embadded na arduino lub sterowniku pralki na mikrokontrolerze, tak jest. Nie powinno się więc generalizować i uogólniać, lecz dostosowywać do aktualnej sytuacji i analizować!

Mnie to przeraża , że można tak pomyśleć, że 32MB na STACK’u to nie dużo, dla mnie to nieskończoność.

W systemach takich jak Linux/Windows używany jest mechanizm translacji pamięci: MMU. Dzięki niemu w trybie chronionym (user space), gdzie program widzi tylko swoją przestrzeń adresową i myśli, że jest jedynym odpalonym programem, STACK może się rozrosnąć do dużych rozmiarów, co jest często nadużywane przez niedoświadczonych programistów. Jeżeli ów programista zdaje sobie z tego sprawę, że pisze kod, który nie będzie wszędzie działał, to ok, gorzej, że o tym może nie wiedzieć.

Przykładowo sterownik dla tego systemu, który działa w trybie rzeczywistym (już wtedy bez wsparcia MMU),
widzi pamięć całego systemu, wtedy dopiero wychodzi, dlaczego na rozmiar STACK’a tak trzeba uważać, i to pomimo tego, że na pokładzie mamy gigabajty RAM’u.

---

Prosty przykład, moj PC, może stary, ale to nie jest ani Arduino ani Pralka:

CPU:i7-3770, RAM:32GB, SSD:2TB, SYSTEM:Ubuntu 20.04.6 LTS

Prosty nic nierobiący sterownik driver.c dla linuxa, który w funkcji startującej definiuje tablicę na STACK’u o rozmiarze 32KB (32 kilo bajtów).

Po załadowaniu tego sterownika do systemu:

# insmod driver.ko

tylko przez to, że ten program był tak nieuprzejmy, że skorzystał “aż” z 32KB na STACK’u, wszystko się wiesza, cały system jest martwy. Pozostaje tylko reset całego komputera.

Generlanie, jest taka opinia, że dobry kod to jest taki, który jest “przenaszalny”, tworzenie dużych danych na STACK’u jest czymś wręcz przeciwnym.

Konkludując, trzeba jak najbradziej uważać na rozmiar STACK’a.

---

Jeżeli chodzi o kursy programowania to nie będę się spierał, fajnie że są, lubię je pooglądać, czasami można się czegoś nowego dowiedzieć, a te Pana Mirosława Zelenta są specyficzne i mają swój urok, może dlatego, że czasami potrafią wkurzyć zaawansowanych, ale tak jest we wszystkich dziedzinach.

Osobiście kiedyś korzystałem z kursu MZ do nauki CSS’a, nie wiem, czy tam jest wszystko wytłumaczone precyzyjnie i idealnie, ale efekt był taki, że mi się przydał, byłem w stanie coś tam zrobić.

---

Pzdr.