 |
www.mimuw90.fora.pl
Forum dla pierwszego roku wydziału MIM UW
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Phoenix
Dołączył: 20 Paź 2009
Posty: 4
Przeczytał: 0 tematów
|
 Wysłany: Wto 0:00, 17 Lis 2009 Temat postu: |
|
|
Powiedzmy, ze potrafie wykazac poprawnosc dla przypadku gdy nasze "n" jest nieparzyste badz parzyste niepodzielne przez 4. Zas nie mam pojecia jak wykazac dokladnie, ze nie da sie odwrocic tego procesu przy n bedaca wielokrotnoscia "4"... bo moze istnieje jakis ekstremalnie niewiarygodny kod, na ktory nikt nie byl w stanie dotad wpasc!
Maybe you know me, but then, maybe you don't!
|
|
| Powrót do góry |
|
 |
|
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Savick
Dołączył: 18 Sie 2009
Posty: 8
Przeczytał: 0 tematów
|
| Wysłany: Wto 0:25, 17 Lis 2009 Temat postu: |
|
|
kolega, kolega:) zgadzam się z Phoenixem, co do tej odwracalności (jestem tym, który to "burzliwie" odwracał ) (w ogólnym przypadku dla n: 4|n się nie da <mogę pokazać, że zazwyczaj istnieje wiele równoważnych ciągów początkowych> - aczkolwiek istnieją sytuacje szczególne, kiedy da się odtworzyć - ale wynika to tylko z przyjętych ograniczeń (dziedziną są parzyste liczby dodatnie))
Co do 19: w a) nie sortuję, w b) sortuję.
Dr Chrząstowski pisał na forum, że 19b było na olimp, jest trikowe i do znalezienia w niebieskiej książeczce - jak ktoś posiada, niech wrzuci:)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
mery
Informatyka
Dołączył: 13 Sie 2009
Posty: 41
Przeczytał: 0 tematów
|
| Wysłany: Wto 14:57, 17 Lis 2009 Temat postu: |
|
|
to gdyby wam się chciało napisać kod tego 6, to ja bym była bardzo wdzięczna i bym z przyjemnością obejrzała. (najchętniej razem z dowodem, że jak n mod 4 = 0, to się nie da) ;)
Ostatnio zmieniony przez mery dnia Wto 15:39, 17 Lis 2009, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
mery
Informatyka
Dołączył: 13 Sie 2009
Posty: 41
Przeczytał: 0 tematów
|
| Wysłany: Wto 17:20, 17 Lis 2009 Temat postu: |
|
|
hm. da się liniowo znaleźć minimalną wartość bezwzględną różnicy dwóch elementów nieposortowanej tablicy?
Ostatnio zmieniony przez mery dnia Wto 17:21, 17 Lis 2009, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Krzysiek
Dołączył: 17 Lis 2009
Posty: 2
Przeczytał: 0 tematów
|
| Wysłany: Wto 17:35, 17 Lis 2009 Temat postu: |
|
|
hmmm, starałem się znaleźć haczyk i nie udało się
czy nie wystarczy znaleźć najmniejszego i największego elementu tablicy? (dowodem może być interpretacja geometryczna)
czy jednak dałem się na coś nabrać?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
mery
Informatyka
Dołączył: 13 Sie 2009
Posty: 41
Przeczytał: 0 tematów
|
| Wysłany: Wto 17:46, 17 Lis 2009 Temat postu: |
|
|
|
jeśli to odpowiedź na moje pytanie, to ja nie mówię o zadaniu 20. (ani żadnym innym właściwie), tylko tak sobie nie na temat o MINIMALNEJ różnicy (tablica nieposortowana, liczby nieujemne. a chyba nawet dodatnie).
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Savick
Dołączył: 18 Sie 2009
Posty: 8
Przeczytał: 0 tematów
|
| Wysłany: Wto 17:53, 17 Lis 2009 Temat postu: |
|
|
mi też się nie udało
przechodzisz przez tablicę szukając maxa, a potem mina (albo obu jednocześnie) najw.wart.bzwzgl=max-min
EDIT: ajć, sorki, zasugerowaliśmy się zadaniem przygotowawczym... hmm pytanie, które postawiłaś troszkę nawet nawiązuje do zadania 19b - na razie nie znam odp.
19b da się zrobić znajdując analogię między naszym problemem, a liczbami Fibonacciego - zauważając pewną właściwość możemy za pomocą łatwych operacji stwierdzić, że:
albo 1) da się zbudować trójkąt na pewno,
albo 2) nie wiemy czy się da, ale wtedy n jest stosunkowo małe (porównywalne z logarytmem wartości największego elementu, który z kolei jest ograniczony przez pojemność Integera) - skoro n jest rzędu logarytmicznego to to, na co wcześniej wpadliśmy ma złożoność loga*log(loga)+loga (gdzie a to rozmiar najw. elem), czyli całkiem przyzwoitą (oczywiście n~=loga)
Ostatnio zmieniony przez Savick dnia Wto 17:59, 17 Lis 2009, w całości zmieniany 2 razy
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hanys
JSIM
Dołączył: 13 Sie 2009
Posty: 4
Przeczytał: 0 tematów
Skąd: Mikołów
|
| Wysłany: Wto 18:01, 17 Lis 2009 Temat postu: |
|
|
|
to że to nie działa dla n mod 4=0 to sie dowodzi latwo na macierzach. ale nie wiem jak moze to zrobic informatyk, bo przeciez wiekszosc nie potrafi liczyc...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
mery
Informatyka
Dołączył: 13 Sie 2009
Posty: 41
Przeczytał: 0 tematów
|
| Wysłany: Wto 18:04, 17 Lis 2009 Temat postu: |
|
|
| Savick napisał: | | pytanie, które postawiłaś troszkę nawet nawiązuje do zadania 19b - na razie nie znam odp.:) |
ano, nawiązuje nawet bardzo, bo właśnie do niego mi to potrzebne. a dwóch elementów zwykle się przyjemniej szuka niż trzech. ;)
| Savick napisał: | | 19b da się zrobić znajdując analogię między naszym problemem, a liczbami Fibonacciego (...) |
o kurwa. co?! ;p
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
asiabej
Dołączył: 12 Paź 2009
Posty: 2
Przeczytał: 0 tematów
|
| Wysłany: Wto 18:16, 17 Lis 2009 Temat postu: |
|
|
|
gdyby komus chcialo sie napisac kod do 6 rowniez bylabym bardzo wdzieczna bo mi to jakos nie idzie szczerze mowiac
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Phoenix
Dołączył: 20 Paź 2009
Posty: 4
Przeczytał: 0 tematów
|
| Wysłany: Wto 19:22, 17 Lis 2009 Temat postu: |
|
|
Zadanko 6 w kodzie, prosze uprzejmie:
| Kod: | // By Phoenix. Enjoy.
program zad6;
const M=30;
var i,j,k,temp,N:integer;
var A,B:array[1..M]of integer;
function power(A:integer; B:integer):integer;
var ip,temp:integer;
begin
temp:=1;
for ip:=1 to B do temp:=temp*A;
power:=temp;
end;
begin
writeln('Uwaga, program pracuje na tabliach najwyzej 30-elementowych.');
writeln('Podaj wielkosc tablicy A: ');
readln(N);
if N mod 4 = 0 then
begin
writeln('Program failure. Dla tablicy o podanej wartosci nie mozna uzyskac pierwotnych wartosci.');
halt
end;
for i:=1 to N do
begin
write('Podaj wartosc ', i,'. elementu z tablicy A: ');
readln(A[i]);
end;
for k:=1 to N do
begin
i:=k+1;
if i>N then i:=i mod N;
temp:=0;
if odd(N) then
begin
for j:=1 to N do
begin
temp:=temp - A[i]*power(-1,j);
Inc(i,2);
if i>N then i:=i mod N;
end;
end else
begin
for j:=1 to (N div 2) do
begin
temp:=temp - A[i]*power(-1,j);
Inc(i,2);
if i>N then i:=i mod N;
end;
end;
B[k]:=temp
end;
writeln('Pierwotne wartosci tablicy A to:');
for i:=1 to N do
begin
A[i]:=B[i];
writeln('A[', i,'] = ', A[i]);
end;
end.
|
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Maxymilian
Informatyka
Dołączył: 23 Sie 2009
Posty: 63
Przeczytał: 0 tematów
|
| Wysłany: Wto 19:26, 17 Lis 2009 Temat postu: |
|
|
analogia z liczbami fibonacciego ciekawa, ale nie można zakładać, że jestesmy ograniczeni integerem...przynajmniej nie sądze, że rozwiązanie, które by to wykorzystywalo, byloby bardzo dobre.
a co do zad 20:
1. jesli chodzi o maxymalna róznice w tablicy P(posortowana) to sie robi w czasie stałym
2. jesli max w tablicy A(nieposortowana) to można zrobić liniowo
3. jeśli min różnica RÓŻNYCH elem w P, to liniowo
4. trudna jest dopiero min różnica w A , co znaczy że profesor musiał być pijany, zeby walnąć dwa błędy w jednym zadaniu...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
asiabej
Dołączył: 12 Paź 2009
Posty: 2
Przeczytał: 0 tematów
|
| Wysłany: Wto 20:28, 17 Lis 2009 Temat postu: |
|
|
|
dzieki wielkie!
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Savick
Dołączył: 18 Sie 2009
Posty: 8
Przeczytał: 0 tematów
|
| Wysłany: Wto 21:53, 17 Lis 2009 Temat postu: |
|
|
Może 20. ma być banalne i tyle:)
Nawet jak nie jesteś ograniczony integerami to i tak otrzymujesz taką złożoność jaką napisałem (w zależności od a), więc chyba nie jest źle - a źródło miałem naprawdę wiarygodne, myślę, że o to rozwiązanie właśnie chodziło.
Ma ktoś niekwadratowe rozwiązania do 36 i 40?
|
|
| Powrót do góry |
|
|
|
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Szukaj
Użytkownicy
Grupy
Galerie
Rejestracja
Zaloguj się, by sprawdzić wiadomości
Zaloguj
