tak ostatnio sobie myslalem, nawet mi sie przysnilo:
zadaniem algorytmu jest na koncu pliku zapisanie jego rozmiaru slownie. ale trzeba tez uwzglednic, ze ten zapis jego rozmiaru na koncu zwiekszy rozmiar tego pliku. przykladem poprawnego pliku moze byc:
1szesc
1 to pierwotna zawartosc pliku, a te "szesc" zwieksza plik o 5 bajtow, co lacznie daje 6 :)
mam nadzieje, ze napisalem dosc zrozumiale :) wlasnie mi sie snilo, ze pisalem taki program :D
Ale wiesz, że nie zawsze to jest możliwe, a czasem niejednoznaczne?
Zapisz pliki (żadna liczba nie będzie poprawna):
0, 1, 2..
I patrz na to (dopisanie obu liczb jest poprawne):
Nsiedem
Ndziewięć
Kolorowych <font color="darkred">s</span><font color="green">n</span><font color="blue">ó</span>w..
tak, ja wiem. w snach wszystko mozna, ale realnie nie:/ no ale nie wazne. ten algorytm nie ma byc przydatny komus. chodzi o samo wygenerowanie pliku na podstawie innego. to, ze moze byc kilka mozliwosci dla jednego pliku, to nie problem. najwazniejsze, zeby format tego pliku byl poprawny. problem alogytmiczny jaki tu podalem potraktujcie jako zabawe dla umyslu :)
tja, no ale w powyższym wypadku prawidłowe jest IMO tylko 1sześć bo chodzi o najmniejszą liczbę, czyli że ważniejsze są jakby dane niż ta dopisana liczba
ja kiedyś się głowiłem czy jest możliwe dopisanie do końca pliku CRC tego pliku :>
a skoro masz sny w których programujesz to oznaka żebyś sobie na jakiś czas dał spokój
Adamo, o CRC też myślałem, ale na jawie oczywiście.
Dobre zagadnienie na konkurs (to z CRC :> )
Zagadnienie dla dzieci z gimnazjum:
lenf - długość pliku
int k;
for(k = 1; k != lenSlownie(k + lenf); k++)
;
// k+lenf -> rozmiar pliku z dołączonym tekstem
funkcja: lenSlownie(int n);
zamienia liczbę 'n' na tekst i zwraca jego długość, np.:
n = 7 -> 'siedem' -> 6
n = 123 -> 'sto dwadzieścia trzy' -> 20 (lub 18 - bez spacji)
n = 1234567899:
'miliard dwieście trzydzieści cztery miliony pięćset sześćdziesiąt siedem tysięcy osiemset dziewięćdziesiąt dziewięć' -> ponad 100
albo on nie zrozumial, albo ja jego nie rozumiem :O
Co tu jest do rozumienia? :D
nie skumałeś że chodzi o napis SŁOWNIE.
hmmm.. Przychodzi mi do głowy jak to zrobić w assmie. Możnaby napisać do tego makro, ale jesli chodzi o jezyki inne niż FASM to ci nie pomogę...
Dream Maker napisał(a)
nie skumałeś że chodzi o napis SŁOWNIE.
Co? Kto nie skumał? Ja?! :[
A co tam robi funkcja lenSlownie!?
Taka funkcja to prosta sprawa - problem dla gimnazjalisty (a może nawet gimnazjalistki :D ).
Na koncu pliku ma byc slownie (a i owszem) ale dlugosc pliku plus dlugosc tego "slownie".
W końcu to maciuś .. ale chyba z "Klanu" [green]
spc napisał(a)
Na koncu pliku ma byc slownie (a i owszem) ale dlugosc pliku plus dlugosc tego "slownie".
przecież tak jest.
oczywiście nie zapisuję tego, a jedynie obliczam co trzeba.
chcesz zapis to masz:
zapisz_na_koncu_pliku(plik, slownie(nowadlugoscpliku));
no i co teraz? :[
Deti napisał(a)
W końcu to maciuś .. ale chyba z "Klanu" [green]
lekko go pojechales :P ale czy slusznie?
moze tak:
x - wielkosc pliku
k - ilosc liter w rozmiarze pliku = lenSlownie(f)
f - nowa wielkosc pliku = x + k
k = lenSlownie(x + k))
i teraz w petli zwiekszamy k, az warunek bedzie prawdziwy.
na razie nie widze bledu. jezeli zauwazycie blad, to piszcie dokladnie, co jest zle.
//juz zauwazylem blad, ale go poprawilem, z rozpedu napisalem cos zle. tak czy siak, to co napisal macius jest dobrze.
Dobra.
Widzę, że natrafiłem na bardzo 'odpornych'.
jest taka pętla:
for(k = 1; k != lenSlownie(k + lenf); k++) ;
lenf - początkowa długość pliku
dla lenf = 1 idzie tak:
k = 1, lenSlownie(1+1) = len('dwa') = 3
k = 2, lenSlownie(2+1) = len('trzy') = 4
k = 3, lenSlownie(3+1) = len('cztery') = 6
k = 4, lenSlownie(4+1) = len('pięć') = 4
czyli rozwiązaniem jest plik o zawartości: 'xpięć'
dla lenf = 5 idzie tak:
k = 1, lenSlownie(1+5) = len('sześć') = 5
k = 2, lenSlownie(2+5) = len('siedem') = 6
k = 3, lenSlownie(3+5) = len('osiem') = 5
k = 4, lenSlownie(4+5) = len('dziewięć') = 8
k = 5, lenSlownie(5+5) = len('dziesięć') = 8
k = 6, lenSlownie(6+5) = len('jedenaście') = 10
k = 7, lenSlownie(7+5) = len('dwanaście') = 9
k = 8, lenSlownie(8+5) = len('trzynaście') = 10
k = 9, lenSlownie(9+5) = len('czternaście') = 11
k = 10, lenSlownie(8+5) = len('piętnaście') = 10
ćwiczcie dalej - zasrańcy. :D </cpp>
No fucktycznie chyba oka. Jakiegos zacmienia dostalem, sorki.
maciuś napisał(a)
for(k = 1; k != lenSlownie(k + lenf); k++) ;
lenf - początkowa długość pliku
...</cpp>
No, ale czy rozwiązanie typu brutal force jest rozwiązaniem w pełnym tego słowa znaczeniu? IMO nie, bo co jeśli plik będzie ważył kilkaset MB?
Obawiam sie ze ciezko bedzie cos innego niz brutal force. Nie wyprowadzisz funkcji na dlugosc "slownie" w zaleznosci od wielkosci pliku.
No właśnie wczoraj zastanawiałem sie nad matematycznym rozwiązaniem problemu. Jednak wczoraj to kaca miałem i wymyśliłem tylko to, że można by zoptymalizować kod, który podał maciuś tak by nie zaczynał od 1 tylko od najmniejszej możliwej liczby. Można by też w sumie wyeliminować przypadki, w których dana liczba na pewno nie będzie rozwiązaniem. IMHO to na początku powinniśmy przyznać każdej cyfrze oraz takim przyrostkom jak dziesiąt, set etc odpowiednią wartość równą jego długości. Następnie posortować je i dopiero wtedy brać sie za szukanie odpowiedniej liczby. Godny uwagi jest tu fakt, iż możemy mieć więcej niż jedno rozwiązanie.
odpowiedz moze byc jednoznaczna i prosta, a algorytm niezbyt skomplikowany, o ile mozesz za liczba slownie wstawic dowolna ilosc znakow np. spacji :)
CyberKid napisał(a)
No, ale czy rozwiązanie typu brutal force jest rozwiązaniem w pełnym tego słowa znaczeniu? IMO nie, bo co jeśli plik będzie ważył kilkaset MB?
Rozmiar pliku nie jest problemem.
Pętla wykona się góra sto razy - ale czy zawsze się skończy(?)
lenf = 500,000,000; len('pięćset milionów ') = 17
Jeśli 'k' przejdzie powyżej kilkadziesiąt (lub sto kilkadziesiąt), to będzie już tak rosnąć do nieskończoności - nazwy liczb nigdy nie będą dłuższe niż sto/dwieście znaków.
Nawet dla 999,999,999,999,999 -> 'dziewięćset dziewięćdziesiąt dziewięć' x 4 + długość słów: 'tysięcy', 'milionów', 'miliardów', ... długość to około 180
Dlatego optymalizacja nie jest tu potrzebna - wystarczy przerwać dla k > 300,
a te 300 obliczeń to czas < 1ms.
Ciekawe jaka jest najmniejsza liczba (długość pliku), dla której nie ma rozwiązania. :)
Zero - napisz to słownie, by było rozwiązanie.. Nie da się, a plik taki może istnieć.
3 = 'tży', trochę nieortograficznie, ale jest 8-O
w wersji angielskiej:
4 = 'four'
w rosyjskiej:
3 = 'tri'