Zaloguj się, aby obserwować  
Anonim_ecd01e12338b9d94a1a513fa581ad6b292a862bb1c126c31d561978527500a64

Matematyka

1442 postów w tym temacie

Dnia 28.10.2007 o 13:39, Bimbermistrz napisał:

Widzę, ale nie jestem pewien, czy można z tego zrobić algorytm dla obojętnych n i k. W każdym
razie dzięki :)


Na pewno się da, problemem jest tylko ograniczony zakres - i nawet unsigned long long int może okazać się niewystarczający. Rozwiązania takiego problemu widzę dwa:
- pierwsze napisanie klasy zawierającej mnożenie i dzielenie liczb o dowolnej długości (czyli nie posiadającej zakresu)
- stworzenie (dynamiczne) tablicy boolowskiej o wielkości k (gdy k<n) i w każdym kroku dzielenie przez maksymalną ilość dzielników określanych przez poszczególne komórki tablicy - i wtedy zmiana w odpowiedniej komórce tablicy wartości z false na true, która mówiłaby właśnie o wykorzystaniu dzielników. Oczywiście trzeba wcześniej sprawdzać, czy dzielenie modulo nie daje reszty, żeby nie stracić jakiś informacji o liczbie.

Z tym, że ten drugi sposób, o ile jest prostszy w implementacji, to i tak nie pomoże, gdy ilość takich kombinacji przekroczy zakres.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

5 min na edycję to za mało ;/

Oczywiście patrząc na ten problem z punktu optymalizacji, idealnym wyjściem byłoby połączenie tych dwóch przypadków - dzielenie całkowite (ze sprawdzaniem modulo) skracałoby nam liczbę, przez co mnożenie byłoby szybsze bo brałyby udział w nim mniejsze liczby, a własna klasa uchroniłaby nas przed przekroczeniem zakresu i "przekręceniem" licznika.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 28.10.2007 o 14:19, vBoguSv napisał:

- stworzenie (dynamiczne) tablicy boolowskiej o wielkości k (gdy k<n)


Ech... znowu to ograniczenia edycji. :/
To nie jest do końca dobre. Oczywiście wielkość tablicy powinna być określona przez k lub n-k, w zależności od tego które jest mniejsze. W końcu skracać wypadałoby zawsze z tą silnią, która jest większa.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Powinno być dobrze:

#!/usr/bin/env python

k=3
n=1000
wynik=1

if (k<(n-k)):
...for i in range ((n-k+1),(n+1)):
......wynik=wynik*i
...wynik=wynik/k
else:
...for i in range ((k+1),(n+1)):
......wynik=wynik*i
...wynik=wynik/(n-k)
print wynik


Część, która będzie skracana w ogóle nie jest obliczana.
P.S. Potrójne kropki zastępują wcięcia kodu.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Niestety nie znam pythona, ale nie rozumiem tylko tych linii (resztę wydaje mi się, że rozumiem):

Dnia 28.10.2007 o 19:06, Treant napisał:

...for i in range ((n-k+1),(n+1)):
...for i in range ((k+1),(n+1)):


Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 28.10.2007 o 20:27, Bimbermistrz napisał:

> ...for i in range ((n-k+1),(n+1)):

Pętla do n-k do n ze zmienną sterującą i zwiększaną o 1 w każdym przebiegu. To +1 przy obu krańcach pętli wynika tylko i wyłącznie ze specyfiki Pythona.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 28.10.2007 o 13:39, Bimbermistrz napisał:

Widzę, ale nie jestem pewien, czy można z tego zrobić algorytm dla obojętnych n i k. W każdym
razie dzięki :)


Tu zapisany w c++ algorytm (i działającą funkcję jednocześnie), która liczy kombinacje, skracając licznik z mianownikiem kiedy to tylko możliwe, dzięki czemu trochę zwiększa się jej użyteczność. Z opisem wszystkich fragmentów, co do których mogą być wątpliwości.

Oczywiście mając już tą funkcję, żeby zapewnić jej dużo większą niewrażliwość (w sensie przekręcania licznika) na długość wyniku, można łatwo rozbudować ją o odpowiednią klasę operacji na liczbach całkowitych o nielimitowanym zakresie. Wystarczy unsigned long long int podmienić na nazwę klasy, a sama klasa musi posaidać przeciążone operatory +, -, %, =, !, /=, *=, <, <=, >, =>, ++, --, o takim samym znaczeniu jak w przypadku standardowych intów.

Z warunków początkowych funkcji ważne jest to, żeby argumenty spełniały jedną nierówność: k <= n.

unsigned long long int Kombinacja (unsigned long long int k, unsigned long long int n)
{
unsigned long long int wielkosc, mianownik, wynik = 1;

/*
wielkosc to rozmiar naszej tablicy przechowującej informacje o dzielnikach z mianownika
mianownik to licznik czynników z mianownika, których nie skróciliśmy
a unsigned long long int bo ma dość duży zakres, jak na 64-bitową liczbę przystało
*/
bool * tab;
//wskaźnik na tablice czynników z mianownika
if (n-k > k) wielkosc = k;
else wielkosc = n - k;

//sprawdza które wyrażenie jest mniejsze, żeby na początku skrócić z większym
if (wielkosc > 1)
{
tab = new bool[++wielkosc];

/*
ustala tablice na odpowiednia ilość elementów
zwiększam wielkosc, ponieważ w C++ tablice zaczynają się indeksem 0, a u mnie właśnie indeks będzie informacja o czynniku.
mógłbym tego nie zwiększać w tym miejscu, ale wtedy za każdym razem kiedy potrzebowałbym skorzystać z wartości czynnika musiałbym dodawać 1 do wartości indeksu, a to za dużo zbędnej roboty dla komputera
*/
mianownik = wielkosc - 2;
/*
indeksy 0 i 1 nas nie interesują, dlatego liczba ważnych czynników jest mniejsza o 2 od wielkości tablicy
*/
for (unsigned long long int j = 0; j < wielkosc; j++) tab[j] = true;
//wypełnianie tablicy informacja, ze poszczególne czynniki nie są jeszcze skrócone
for (unsigned long long int i = n - mianownik; i <= n; i++)
//informacja o początku i końcu elementów do mnożenia z licznika, raczej jasna
{
wynik *= i;
//mnożenie wyrażenia z licznika
if (mianownik)
//sprawdza czy są jeszcze jakieś czynniki w mianowniku do skrócenia
for (unsigned long long int j = 2; j < wielkosc; j++)
if (tab[j] && !(wynik%j))
{
wynik/=j;
tab[j] = false;
mianownik--;
}

/*
Przegląda tablice czynników, w poszukiwaniu istniejący (warunek: tab[j] ),
które na danym etapie można skrócić (warunek: !(wynik%j) - czyli nie ma reszty z dzielenia wyniku przez j)
Jeśli znajdzie indeks spełniający takie założenie, to dzieli przez niego wynik,
ustawia informację o skróceniu konkretnego czynnika i zmniejsza licznik ilości czynników które trzeba skrócić
*/
}
}
return wynik;
}

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Poprawiłem błąd w python''owym kodzie i przepisałem go (w koślawy sposób) na C++ , żeby było Ci łatwiej zrozumieć. Ogólnie chodzi o to, żeby skrócić n! z k! lub (n-k)! - zależy która z tych dwóch liczb jest większa i mnożyć tylko to, co zostanie po skróceniu. Potem wystarczy tę dużą liczbę podzielić przez odpowiednio (n-k)! lub k!. Może jeszcze udoskonalisz poniższy poniższy program:

#include <iostream>

int main ()
{

int k=3;
int n=1000;
int wynik=1;

if (k<(n-k))
{
for (int i=(n-k+1);i<n+1;i++)
{
wynik=wynik*i;
}
for (int i=1;i<k+1;i++)
{
wynik=wynik/i;
}
}
else
{
for (int i=(k+1);i<n+1;i++)
{
wynik=wynik*i;
}
for (int i=1;i<(n-k+1);i++)
{
wynik=wynik/i;
}
}
std::cout << wynik;
std::cout << "\n";
}

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Wydumałem jeszcze przed zaśnięciem, że wynik można obliczyć w jednej pętli (co daje dodatkową korzyść, bo będzie on na bieżąco dzielony). Wyglądałoby to mniej więcej tak:
for (int i=(n-k+1);i<n+1;i++)
{
wynik=wynik*i/(i+k-n);
}

i tak:
for (int i=(k+1);i<n+1;i++)
{
wynik=wynik*i/(i-k);
}


o ile gdzieś się nie pomyliłem. No i ta końcówka programu... std::cout << wynik << "\n";

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 29.10.2007 o 09:18, Treant napisał:

Wydumałem jeszcze przed zaśnięciem, że wynik można obliczyć w jednej pętli

Nie, nie można. Zapominasz że dzielenie całkowitoliczbowe nie jest bezstratne, bo gdy (i+k-n) lub (i-k) nie będą dzielnikami wynik''u to wtedy stracisz informację o reszcie z dzielenia, co może (i w większości przypadków będzie) wypaczyć wynik. Dlatego to co zaproponowałem 2 posty wyżej wydaje mi się najprostszą możliwą wersją ze skracaniem licznika z mianownikiem - oczywiście może są lepsze sposoby, można byłoby też "uczyć" program myśleć po ludzku przy skracaniu, a to już zahacza o AI i jest pewnie dużo bardziej skomplikowane.

Co prawda robi się już trochę oftop przechodzący z matmy na programowanie (choć to bez matmy nie istnieje) i głupio byłoby go tak ciągnąć, ale póki ciągle zahacza o wyrażenia matematyczne to może moderatorzy nie będą mieli nam tego za złe ;)

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 29.10.2007 o 14:04, vBoguSv napisał:

Nie, nie można. Zapominasz że dzielenie całkowitoliczbowe nie jest bezstratne, bo gdy (i+k-n)
lub (i-k) nie będą dzielnikami wynik''u to wtedy stracisz informację o reszcie
z dzielenia, co może (i w większości przypadków będzie) wypaczyć wynik.

Teoretycznie tak. Zauważ jednak, że dzielniki rozpoczynają się od jedności, podczas gdy dzielna rośnie znacznie szybciej. Spróbuję znaleźć takie k oraz n, przy których dochodzi do takiej sytuacji.

Dnia 29.10.2007 o 14:04, vBoguSv napisał:

Co prawda robi się już trochę oftop przechodzący z matmy na programowanie (choć to bez matmy
nie istnieje) i głupio byłoby go tak ciągnąć, ale póki ciągle zahacza o wyrażenia matematyczne
to może moderatorzy nie będą mieli nam tego za złe ;)

Na pewno nie, bo Bimbermistrz wspominał o tym, że ma właśnie napisać program, który obliczy mu wartość takiego wyrażenia.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 29.10.2007 o 14:45, Treant napisał:

Teoretycznie tak. Zauważ jednak, że dzielniki rozpoczynają się od jedności, podczas gdy dzielna
rośnie znacznie szybciej.

Może masz racje, ale to nie jest bezpieczne założenie bo może trafić się przypadek, w którym jednak coś z wyniku utracimy - muszę to jeszcze raz przeanalizować i jeśli jakiś znajdę to na pewno się podzielę. Co prawda nie mam pewności jeszcze że taki w ogóle istnieje, ale można przypuszczać że jest to możliwe. A programy generalnie nie powinny zawierać błędów, których wystąpienia nie potrafimy wcześniej przewidzieć i z góry naprawić - i właśnie dlatego negowałem twoje rozwiązanie, przyznam, może zbyt pochopnie. Przed chwilą sprawdziłem kilka zestawów wartości wejściowych i wyniki podawane przez nasze funkcje się nie różnią - z tym, że nazwać tego porządnym testowaniem nie można, bo nie przygotowałem (więc i może nie sprawdziłem) sobie potencjalnych "zagrożonych" zestawów, mogących wywołać błąd.

Ale zakładając, że szansy na błąd nie ma to nawet, że gdybyś zamiast intów korzystał z unsigned long long intów, to jednak szybciej będzie "przekręcać" licznik z uwagi na przekroczenie zakresu - choć twoja funkcja jest dużo prostsza i możliwe że szybsza, ale przy tak niewielkim zakresie jaki daje liczba zapisana w 64bitach jest to nie do zauważenia.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Program napisałem, omijając liczenie tego dość wrednego przykładu. Po prostu na początku wczytałem sobie dwuwymiarową tablicę symulującą trójkąt Pascala, a potem wystarczyło dla podanego n i k wypisać tablica[n-k][k] :)

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Dostałem dzisiaj dosc sporą prace domową i nie wiem jak sie za to zabrac pomozecie?:D.


Zad 1)Wykonaj wskazane działania
a)4x(x-6z+2y-5)
b)-3z(7x+3y-9z)
c)-y(7x-5y+4z+2t)
d)2x(3-4y-2x+5t)
2)
a)(x-2y) (x+2)
b)(3x-2y) (5x-9y)
c)(a-4b) (7a-6b)
d)(2a-7c) (4c-6a)
e)(2z+3b-2) (3z-b+4)

3)Wyznacz wartosci pozostałych funkcji trygonometryczniych kąta alfa wiedząc ze
a)sin alfa=2/3(/-mianownik)
b)cos alfa=0,8
c)tgd=2
d)ctg alfa=5
e)sin alfa=56
e)sin alfa=5
e)sin alfa=0,6
f)cos alfa=1/2
g)sin alfa=3/7


Potrzebuje tego na jutro proszę o szybkie rozwiązanie.Z góry thx:)

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 06.11.2007 o 13:13, Sycylius napisał:

Dostałem dzisiaj dosc sporą prace domową i nie wiem jak sie za to zabrac pomozecie?:D.


Zad 1)Wykonaj wskazane działania
a)4x(x-6z+2y-5)
b)-3z(7x+3y-9z)
c)-y(7x-5y+4z+2t)
d)2x(3-4y-2x+5t)
2)
a)(x-2y) (x+2)
b)(3x-2y) (5x-9y)
c)(a-4b) (7a-6b)
d)(2a-7c) (4c-6a)
e)(2z+3b-2) (3z-b+4)


Jeśli w tych zadaniach nic więcej nie jest napisane to wg mnie trzeba to po prostu poupraszczać (powymnażać nawiasy)
W 1a) byłoby
4x^2-24xz+8xy-20x
Nic innego nie przychodzi mi do głowy, chyba, że jeszcze coś jest w treści zadań (myślę, że sobie z tym dalej poradzisz)

Dnia 06.11.2007 o 13:13, Sycylius napisał:


3)Wyznacz wartosci pozostałych funkcji trygonometryczniych kąta alfa wiedząc ze
a)sin alfa=2/3(/-mianownik)
b)cos alfa=0,8
c)tgd=2
d)ctg alfa=5
e)sin alfa=56
e)sin alfa=5
e)sin alfa=0,6
f)cos alfa=1/2
g)sin alfa=3/7


Co do tego zadania to trzeba pewnie wykorzystać własności funkcji trygonometrycznych, jak np jedynka trygonometryczna czy takie tam.
powiedzmy przykład 1(zamiast alfa wpisze a)
sin(a)=2/3
sin^2(a)+cos^2(a)=1
(2/3)^2+cos^2(a)=1
cos^2(a)=5/9
cos(a)=[sqrt(5)]3
tg(a)=sin(a)/cos(a)=2/sqrt(5)
ctg(a)=1/tg(a)=sqrt(5)/2

I tak dalej (sqrt -> pierwiastek kwadratowy z liczby jakby były wątpliwości)

Dnia 06.11.2007 o 13:13, Sycylius napisał:


Potrzebuje tego na jutro proszę o szybkie rozwiązanie.Z góry thx:)


Mam nadzieję, że podane podpowiedzi pozwolą Ci to skończyć samemu i się do jutra wyrobisz. Bo jak bym Ci to wszystko rozwiązał to się tego nigdy nie nauczysz ;) A to wbrew pozorom są proste rzeczy. W razie jakichś większych kłopotów z którymś przykładem pisz. Jak nie ja to ktoś inny pomoże

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Mam taki problem, czy można w jakiś prosty sposób udowodnić, że: 2e-e^7<0. To są konkretne liczby i można to policzyć, ale podnieść e^7 to dość skomplikowane i trudno komukolwiek wmówić, że na kartce policzyłem... (nawet w przybliżeniu). I drugi podobny przykład: 2e^4-e^9<0.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 11.11.2007 o 16:15, Egan Wolf napisał:

Mam taki problem, czy można w jakiś prosty sposób udowodnić, że: 2e-e^7<0. To są konkretne
liczby i można to policzyć, ale podnieść e^7 to dość skomplikowane i trudno komukolwiek wmówić,
że na kartce policzyłem... (nawet w przybliżeniu). I drugi podobny przykład: 2e^4-e^9<0.

2e-e^7<0
2e<e^7 / :e
2<e^6
e to jest chyba 2.72, więc po podniesieniu do 6 potęgi jeszcze wzrośnie :)

2e^4-e^9<0
2e^4<e^9 / :e^4
2<e^5
Tyż prawda - analogicznie jak w poprzednim zadaniu :)

Wystarczy z własności potęg skorzystać...

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Dnia 11.11.2007 o 16:25, Vel Grozny napisał:

2e<e^7 / :e
2<e^6

Czy nie należy tego rozbić na 2 przypadki? Jeden dla e ujemnego, a drugi dodatniego?

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Utwórz konto lub zaloguj się, aby skomentować

Musisz być użytkownikiem, aby dodać komentarz

Utwórz konto

Zarejestruj nowe konto na forum. To jest łatwe!


Zarejestruj nowe konto

Zaloguj się

Masz już konto? Zaloguj się.


Zaloguj się
Zaloguj się, aby obserwować