Цитата:
Сообщение от Rooslan Khayrov
(Сообщение 493287)
Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 1 до 100.000, на всякий случай напомнив, что простое число - это число, которое делится только на себя и на единицу. Через некоторое время задание было выполнено. Практически все сделали примерно так:
|
Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать:)
Например:
PHP код:
List<int> GetPrimNumber(int n)//n -число до которого необходимо искать простые числа { //Инициализация bool[] z = new bool[n+1]; //0 и 1 не простые числа - сразу же исключаем z[0] = true; z[1] = true; double sqrt = Math.Sqrt(n); int k = 0; int i = 2; //Первое простое число while (i <= sqrt) { k = i; while (k*i <= n) { z[k*i] = true; k++; } //Поиск нового простого числа i++; while ((z[i])&&(i<=sqrt)) { i++; } } //Все простые числа вносятся в новый список: List<int> l = new List<int>(); for (int j = 0; j < n+1; j++) { if (!z[j]) l.Add(j); } return l;//возврат списка с окончательным результатом }
на c# при n=100 000 выполняется уже за 3 миллисекунды:)
смысл алгоритма очень прост: ряд чисел 2,3,4,5,6,7,8,9,10...,n сначала находим первое не перечеркнутое число 2 и перечеркиваем все кратные ему числа 2,3, 4,5, 6,7, 8,9, 10..., ищем следующее не перечеркнутое число -в данном случае 3 и перечеркиваем дополнительно все кратные ему: 2,3, 4,5, 6,7, 8, 9, 10..., теперь ищем следующее не перечеркнутое ит.д. пока не достигнем числа равного корню из n -все не зачеркнутые числа -простые:) -называеться алгоритм Решето Эратосфена
|