Witam, osobiście mam problem z takimi oto 2 zadankami:
1. Załóżmy, że dane są dwie n elementowe tablice A oraz B wypełnione losowo wartościami całkowitymi w porządku niemalejącym oraz dana jest liczba X. Zaproponować i zaimplementować algorytm sprawdzający czy istnieją dwie liczby a, b takie że a+b=X, przy czym liczba a znajduje się w tablicy A natomiast liczba b w tablicy B. Zaproponować algorytm, o możliwie najmniejszej złożoności licznonej liczbą porównań
2. Dla zadanej liczby naturalnej N znaleźć ile liczb pierwszych znajduje się w przedziale [2,N]. Liczb pierwszych poszukiwać można za pomocą algorytmu sita Erastotenesa.
Z 1 zadaniem mecze się już parę ładnych dni, ale z racji iż dopiero zaczynam cos nie coś programować a nasz profesorek nie za bardzo umie nam wiedzę wyłożyć to siedzę w czarnej d...
Co do drugiego zadania udało mi się odnaleźć ten algorytm sita: http://pl.wikipedia.org/wiki/Sito_Eratostenesa ale ni czorta nie wiem jak mam go wpakować do programu ;/
Myślę, ze 1 zadanko jest dość skomplikowane, ale 2 dla wprawionego informatyka to 5 min roboty - a może ma już ktoś podobny programik zrobiony ;]
Z góry dziękuje za udzielona pomoc (prace robiliśmy w programach:MS Visual C++ 2005 Express, MS Visual Basic 2005 Express ale programy z tych zadań mogą być w wersji konsolowej )
1. Załóżmy, że dane są dwie n elementowe tablice A oraz B wypełnione losowo wartościami całkowitymi w porządku niemalejącym oraz dana jest liczba X. Zaproponować i zaimplementować algorytm sprawdzający czy istnieją dwie liczby a, b takie że a+b=X, przy czym liczba a znajduje się w tablicy A natomiast liczba b w tablicy B. Zaproponować algorytm, o możliwie najmniejszej złożoności licznonej liczbą porównań
2. Dla zadanej liczby naturalnej N znaleźć ile liczb pierwszych znajduje się w przedziale [2,N]. Liczb pierwszych poszukiwać można za pomocą algorytmu sita Erastotenesa.
Z 1 zadaniem mecze się już parę ładnych dni, ale z racji iż dopiero zaczynam cos nie coś programować a nasz profesorek nie za bardzo umie nam wiedzę wyłożyć to siedzę w czarnej d...
Co do drugiego zadania udało mi się odnaleźć ten algorytm sita: http://pl.wikipedia.org/wiki/Sito_Eratostenesa ale ni czorta nie wiem jak mam go wpakować do programu ;/
Myślę, ze 1 zadanko jest dość skomplikowane, ale 2 dla wprawionego informatyka to 5 min roboty - a może ma już ktoś podobny programik zrobiony ;]
Z góry dziękuje za udzielona pomoc (prace robiliśmy w programach:MS Visual C++ 2005 Express, MS Visual Basic 2005 Express ale programy z tych zadań mogą być w wersji konsolowej )
