Toreador
Гродненец
Репутация: +22/-0
Offline
Пол:
Сообщений: 226
mode move move
|
|
« : 20 Ноябрь 2006, 00:52:16 » |
|
Итак, самый классный алгоритм для нахождения простых чисел? Хм? Пока ещё не видел круче Эратосфена(до 255)... Program Eratosfen; Const N = 201; {Возможно любое значение 1 < N < 256} Var A, B: Set of 2 .. N; K, P: Integer; Begin { Формирование исходного множества A; B - искомое множество простых чисел, сначала - пустое) A := [2 .. N]; B := [ ]; P := 2; Repeat {Поиск минимального числа в множестве A} while Not (p in A) do p := p+1; {Включение нацденного числа в множество B} b := b + [p]; k := p; {Исключение из A чисел, кратных P} while k<=n do begin a := a - [k]; k := k + p; end until a = [ ]; { Вывод результата, т.е. всех чисел из множества B в порядке возрастания} for p := 2 to n do if p in b then writeln(p) end. Может кто предложит круче?!
|
|
« Последнее редактирование: 23 Ноябрь 2006, 20:31:55 от Toreador »
|
Записан
|
+++++++++++++++++++++++++++++
|
|
|
maxposedon
|
гы-гы-гы ) прежде чем мерятся, доставай всё © кто-то а теперь покажи всем свой алгоритм для чисел > 256, а?)) а то до 256 простые числа и константами забить можно, или по твоему простых чисел > 256 не бывает, или они никаму не нужны? вот так и появляются Горе-паскаль-программисты... а пока (на правах рекламы) max_posedon@Melnikov temp % cat ./prime.rb #!/usr/bin/ruby
require 'mathn'
Prime.new.each do |prime| break if prime > 1000 p prime endP.S. 2Tareador, лучше не позорься, а пиши/выкладывай код на C/C++, хоть кoму-то польза будет
|
|
« Последнее редактирование: 20 Ноябрь 2006, 10:07:44 от maxposedon »
|
Записан
|
|
|
|
7floor
|
maxposedon, и чем ты понтанулся? Алгоритм напиши, а не покажи, что умеешь заюзать готовое. А то, ИМХО, сел в лужу.
|
|
|
Записан
|
Древняя китайская мудрость гласит: "Когда нечего сказать, но очень хочется, скажи древнюю китайскую мудрость!" Я на drive2.ru
|
|
|
maxposedon
|
maxposedon, и чем ты понтанулся? Алгоритм напиши, а не покажи, что умеешь заюзать готовое. А то, ИМХО, сел в лужу. код, был предъявлен лишь из рекламных целей, а за меня не волнуйся, писать такое я умею ... да и суть в том, что существует множество алгоритмов, некоторые быстрые, другие `едят` мало памяти... а для чисел <256, я вообще за массив констант... хотя, сча навояемс...
|
|
|
Записан
|
|
|
|
maxposedon
|
max_posedon@Melnikov ~ % cat prime.cpp #include <vector> #include <iostream> #include <cmath>
using namespace std;
const int val = 1000;
int main() { // primes хранит простые числа vector<int> primes;
// пробегаем диапазон for(int i=2; i<val; i++) { //проверяем просто ли очередное число bool prime = true; int sqrt_i= (int)sqrt(i)+1;
//пытаемся делить на все простые числа, до корня из i for(unsigned int j=0; j<primes.size(); j++) if (i%primes[j]==0) { prime = false; break; } else if (primes[j] >= sqrt_i) break; //если простое, то заносим if (prime) primes.push_back(i); }
//вывод for(unsigned int i=0; i<primes.size(); i++) cout << primes << " "; cout << endl;
return 0; }
ну дабы, не было это просто так... у моего Алгоритма сложность O(N*log(M)), N - кол-во чисел M - кол-во простых чисел
для проверки на простоту проверяется все до N, а тока простые и то до корня из числа поэтому и получаем N*log(M)
|
|
« Последнее редактирование: 20 Ноябрь 2006, 11:20:04 от maxposedon »
|
Записан
|
|
|
|
VooDoo
|
гы, знакомое дело. Кстати когда-то задача была на районной олимпиаде. Были очень большие числа, маленькое время и тихоходный комп. Кстати, ходить можно через одно, зачем проверять чётные... а что именно писал уже не помню
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
Кстати, ходить можно через одно, зачем проверять чётные...
тут шутка в чем, O(N/2*log(M)) == O(N*log(M)) ) ведь при чётных внутренний цикл, не цикл собственно т.е. если ити тока по четным, ускорение составит ~1-5% в зависимости от val (при больших val, `ускорение` уменьшается)... хотя запихнуть в primes 2 и ити нечётным, наверное действительно `кошернее`
|
|
« Последнее редактирование: 20 Ноябрь 2006, 15:53:52 от maxposedon »
|
Записан
|
|
|
|
VooDoo
|
просто в форе сделать (int i=3; i<val; i+=2) а в праймс не надо пихать, если только в конце всё-таки при больших числах мы будем каждый раз делать ненужную работу. Может секунды, но приятно
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
VooDoo
|
на джаве :
int n=100000000;
Started at ->Mon Nov 20 16:53:16 EET 2006 Finish time ->Mon Nov 20 16:57:44 EET 2006 5761454 и плюс 1 и 2 итого 5761456
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
такс, провёл замеры, с выводом всех ~5млн чисел на экран и без) (просто вывод это достаточно долго, а из поста VooDoo, я не понял как он запускал) код (что выше, и с модификацией про нечётность) компилировался g++ -O3 prime.cpp, вывод производился на konsole (такс-у не удалось загрузить проц на 100% из-за всяких там beryl-ов/amarok-ов и прочим) 1. оригинальный, время засекалось с выводом ./a.out 113,96s user 0,62s system 60% cpu 3:09,42 total 2. без вывода ./a.out 112,36s user 0,15s system 76% cpu 2:27,34 total 3. пробег тока по нечетным, с выводом ./a.out 111,49s user 0,83s system 65% cpu 2:52,45 total 4. нечетные, без вывода ./a.out 108,05s user 0,14s system 75% cpu 2:23,24 total
2VooDoo , обрати внимание `оптимизация по нечетным` лежит в границах статистической погрешности .. такс... кажется мы о чем-то/ком-то забыли 2Tareador, а теперь ваш код, и замеры ) ждемс...
|
|
|
Записан
|
|
|
|
VooDoo
|
у меня был без вывода, без чётных. много времени жрёт вывод:( и надо немножко переделать, завтра выложу. и хочу попробовать на руби, что будет быстрее. Кстати для паскаля, если мне не изменяет память была директива {R-} выключала range check для массива. Очень ускоряла работу с массивами. Это аффтару на заметку
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
ruby сильно сплющит от такого кол-ва объектов, причем полноценных объектов... (`число-дробилки` не его сильная сторона) хотя реализация достаточно красивая будет
max_posedon@Melnikov temp % cat primes.rb #!/usr/bin/ruby
val = 10000 primes = [2]
3.step(val,2) do |i| sqrt_i = i ** 0.5 + 1 primes << i if !primes.find{ |j| (i%j == 0) || (break if j > sqrt_i) } end
p primes
|
|
« Последнее редактирование: 21 Ноябрь 2006, 14:44:07 от maxposedon »
|
Записан
|
|
|
|
VooDoo
|
и джаву расплющило. Отдал ей гиг мозгов, оставил на ночь... Когда пришёл увидел out of memory Да, итераторы в руби очень приятная вещь
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
и джаву расплющило. Отдал ей гиг мозгов, оставил на ночь... Когда пришёл увидел out of memory Да, итераторы в руби очень приятная вещь 2VooDoo , покажи таки Java-код (для меня - чисто посмеятся с языка ) и я не понял, при каких N расплющело то? естественно код должен, создавать массив простых...
|
|
|
Записан
|
|
|
|
Toreador
Гродненец
Репутация: +22/-0
Offline
Пол:
Сообщений: 226
mode move move
|
гы-гы-гы ) прежде чем мерятся, доставай всё © кто-то P.S. 2Tareador, лучше не позорься, а пиши/выкладывай код на C/C++, хоть кoму-то польза будет Да-да-да... началось... ну как же тут без споров какой язык круче?! А? Простой вопрос для тебя: Ты название темы читал, когда заходил и оставлял месаги? На счёт позориться, не знаю, это не тебе решать... (Может ты сразу с детства, уже в утробе матери, знал С/С++?) Ладно, кароче... чё то нет нормальных программистов у нас в Гродно :-?... ...
|
|
|
Записан
|
+++++++++++++++++++++++++++++
|
|
|
VooDoo
|
чё то нет нормальных программистов у нас в Гродно эт ты зря, по крайней мере они были... 2Max : после некоторых оптимизаций получилось такое: int n=100000000; System.out.println(n); System.out.println("Started at ->"+new Date()); ArrayList primes= new ArrayList(); primes.add(new Integer(3)); int i_sqrt; int k=0; Integer subList[]=null; loop:for (int i=5 ; i < n ; i += 2) { i_sqrt=(int)Math.sqrt(i); if (((Integer)primes.get(k)).intValue()<=(i_sqrt)) { k++; subList = (Integer[])primes.subList(0,k).toArray(new Integer[k]); } for (int j = 0; j< k ;j++) { if (i%(subList[j]).intValue()==0) { continue loop; } } primes.add(new Integer(i)); } System.out.println("Finish time ->"+new Date()); System.out.println(primes.size()); } скажу сразу, тут я вырезал кусок из ArrayList и вставлял в простой массив, так получается дешевле в два раза(всё таки массивы быстрее всего:) ) в итоге: 100000000 Started at ->Tue Nov 21 14:36:45 EET 2006 Finish time ->Tue Nov 21 14:38:36 EET 2006 5761454 время почти как сишное
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
VooDoo
|
расплющило его на 1000000000 Toreador ждём примеров на паскале и результатов. Уж больно интересно:)
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
Да-да-да... началось... ну как же тут без споров какой язык круче?! А? Простой вопрос для тебя: Ты название темы читал, когда заходил и оставлял месаги? На счёт позориться, не знаю, это не тебе решать... (Может ты сразу с детства, уже в утробе матери, знал С/С++?) Ладно, кароче... чё то нет нормальных программистов у нас в Гродно :-?... ... 1. споров тут нет, тут пока тока алгоритмы и код, мы ждем код от тебя... 2. да читал, паскаль далеко не рулез - раз, ты все таки хотел больше про алгоритмы - это два 3. решать не мне, а дать совет я думаю я могу) 4. нет программистов? гы-гы, а ты про всех программистов в Гродно что-то знаешь?) ну и вообще говоря всё это мелочи, мы ждем от тебя код, и дело наверное таже не в скорости, а в лаконичности и удобночитаемости
|
|
|
Записан
|
|
|
|
Toreador
Гродненец
Репутация: +22/-0
Offline
Пол:
Сообщений: 226
mode move move
|
Toreador ждём примеров на паскале и результатов. Уж больно интересно:) 1. споров тут нет, тут пока тока алгоритмы и код, мы ждем код от тебя... ну и вообще говоря всё это мелочи, мы ждем от тебя код, и дело наверное таже не в скорости, а в лаконичности и удобночитаемости От меня? хм... И чего вы ожидаете? Супер-мега кода... Нет ребята, Паскаль - это "начальный" язык. С него начинают практически все программисты... Ведь в основном суть то не втом какой язык круче, а в том как ты умеешь его использовать, вернее писать на нём массивные проги... Превращать идею в алгоритм, а потом в программу... Ладно вот вам простенький алгоритм нахождения простых чисел >255... var a:array[1..32000] of integer; n,p,i,j,k:longint;
function prost(n:longint): boolean; var i,j:longint; begin j:=0; for i:=1 to n do if n mod i = 0 then j:=j+1; if j=2 then begin prost:=true; a:=n; end else prost:=false; end;
begin write('Vvedi granicu diapazona: '); readln(k); for n:=1 to k do begin p:=n+1; while not prost(p) do p:=p+1; end; a[1]:=1; for i:=1 to n do if (a<>0) then write(a:5); end.
Можно усовершенствовать, упростить, но делал на скорую руку... Теперь можете критиковать!........
|
|
|
Записан
|
+++++++++++++++++++++++++++++
|
|
|
Toreador
Гродненец
Репутация: +22/-0
Offline
Пол:
Сообщений: 226
mode move move
|
Ладно... фиг с ним... Алгоритм есть... вроде есть... поехали дальше... Всегда сложность составляют в олимпиадных задачах графы... Ладно пойду поищу нормальную задачу на кротчайшие пути и т.п....
|
|
|
Записан
|
+++++++++++++++++++++++++++++
|
|
|
VooDoo
|
так сколько времени твой алгоритм будет считать при n=100000000?
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
так сколько времени твой алгоритм будет считать при n=100000000? а самому посчитать?) у него следующий алгоритм (своё `крутое` решето эратосфера он решил не реализовывать) каждое число(n) из диапозона 1 .. k, он делит на _все_ числа из диапозона 1..n, и убеждается что делителей ровно 2. итого делаем выводы 1. алгоритм жутко убогий, и даже этот простейший алгоритм он ужасно реализовал 2. сложность алгоритма O(N*N) сл-но... при N=100млн =10^8, у него будет 10^16 операций на процессоре в 1Ghz это займет примерно 10^5 секунд = 1666мин = 27часов = 1сутки , т.е. это займет несколько суток 2Toreador почитай хоть котова чтоли, а то тебе явно ничего не светит
|
|
|
Записан
|
|
|
|
VooDoo
|
10^16 операций на процессоре в 1Ghz что-то слишком много. Для пня 4 можно считать примерно 1 к 1(Ghz vs. GFLOPS) и то... я бы сказал меньше, но на самом деле от задачи зависит. А с Котова надо начинать...
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
10^16 операций на процессоре в 1Ghz что-то слишком много. Для пня 4 можно считать примерно 1 к 1(Ghz vs. GFLOPS) и то... я бы сказал меньше, но на самом деле от задачи зависит. может я непонятно сформулировал, я считал скока (O-большое) будет выполнятся 10^16 операций (у него N*N сложность) на 1Ghz -проце(O(10^9)-операций в секунду), получилось O(сутки) посчитал вроде правильно
|
|
|
Записан
|
|
|
|
VooDoo
|
ну да, сформулировал совсем не понятно. брррр 10^16 делим на 10^9 = 10^7. 2777 часов = 115 суток
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
ну да, сформулировал совсем не понятно. брррр 10^16 делим на 10^9 = 10^7. 2777 часов = 115 суток каюсь, обсчитался в 100раз)... я тут вспомнил одно выскаывание: Данный процесс будет длится 10^(10^10), вот тока я не помню, толи секунд, толи лет, что в принципе при таких числах не имеет значения © препод по физике
|
|
|
Записан
|
|
|
|
Toreador
Гродненец
Репутация: +22/-0
Offline
Пол:
Сообщений: 226
mode move move
|
Да ну Вас критики... Ща почитаю...
|
|
|
Записан
|
+++++++++++++++++++++++++++++
|
|
|
Toreador
Гродненец
Репутация: +22/-0
Offline
Пол:
Сообщений: 226
mode move move
|
Спасибо чуваки... Чутарик меня разозлили... Правда Котов не помог , но сам допетрил вот до этого алгоритма : var n,p,i,j,k:longint; procedure prost; begin j:=0; for i:=1 to n do begin if n mod i = 0 then j:=j+1; if j>2 then break; end; if j=2 then write(i:10); end; begin write('Vvedi granicu diapazona: '); readln(k); for n:=1 to k do prost; readln; end.
Критикуйте, если есть что???!!!! И вот вам интересная олимпиадная задачка: «Интернет–магазин». Входной файл: shop.in Выходной файл: shop.out В базе данных (далее – БД) Интернет–магазина содержится информация о K приобретенных товарах. Злоумышленник, взломав БД, получил возможность поменять местами между собой: • содержимое полей с данными о цене товаров; • содержимое полей с данными о количестве приобретенных единиц товара. В результате этих действий Интернет–магазин может понести убыток по общей стоимости товаров, который определяется разностью между исходной стоимостью приобретенных товаров в неповрежденной БД и их стоимостью после действий злоумышленника. Определить наибольший убыток по общей стоимости товаров, который может принести злоумышленник владельцам магазина. Формат входных данных. Входной файл shop.in содержит К+1 строк. В первой строке находится число K. В каждой из остальных K строк записаны два действительных числа a и b – соответственно цена за единицу и количество приобретенного товара до действий злоумышленника. Ограничения. 1 ? K ? 1000 0.00 < a ? 1000000.00 0.00 < b ? 1000000.00 Числа a и b содержат не более двух разрядов после десятичной точки. Формат выходных данных: Выходной файл shop.out должен содержать одну строку с искомым количеством убытка по общей стоимости товаров с точностью до четырех разрядов после десятичной точки. Пример файла входных данных: 4 2 2.5 3.5 4 1 2 2.5 5 Пример файла выходных данных (для приведенного выше входного файла): 7.2500
|
|
|
Записан
|
+++++++++++++++++++++++++++++
|
|
|
VooDoo
|
да не надо цикл делать до n. как минимум n/2. больше же чем на n/2 n не разделится.
задачку потом посмотрим
|
|
|
Записан
|
Are you human? - My body is. Do you feel pain? - My body does. ..- --- --- -.. --- ---
|
|
|
maxposedon
|
Правда Котов не помог , но сам допетрил вот до этого алгоритма : var n,p,i,j,k:longint; procedure prost; begin j:=0; for i:=1 to n do begin if n mod i = 0 then j:=j+1; if j>2 then break; end; if j=2 then write(i:10); end; begin write('Vvedi granicu diapazona: '); readln(k); for n:=1 to k do prost; readln; end.
Критикуйте, если есть что???!!!! а!!!... во первых, алгоритм остался почти тот же, реализация тока лучше вот если заменить, проверку, вместо n, до sqrt(n)... и бежать от 2(а не от 1) и выход не при j>2, а при j>0 то уже лучше... НО! сложность будет N*log(N), что правда уже неплохо)), но сё равно в раз 100 медленнее чем у меня, (хотя уже тот факт что 100 это константа , радует) а сл-но опять N*N, и опять ~115 суток при n = 10^8 ты бы думалку включил) вперед читать основы, и попроси своих преподов расказть тебе про сложность алгоритмов, а то умрёшь в неведении... рано тебе еще задачи на графы решать) а мы посмотрим...
|
|
« Последнее редактирование: 25 Ноябрь 2006, 11:24:28 от maxposedon »
|
Записан
|
|
|
|
|