Как вывести число от данного до 10 включительно

Алгоритм нахождения простых чисел

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Источник

Как выбрать случайное число от 1 до 10

Представьте, что вам нужно сгенерировать равномерно распределённое случайное число от 1 до 10. То есть целое число от 1 до 10 включительно, с равной вероятностью (10%) появления каждого. Но, скажем, без доступа к монетам, компьютерам, радиоактивному материалу или другим подобным источникам (псевдо) случайных чисел. У вас есть только комната с людьми.

Предположим, что в этой комнате чуть более 8500 студентов.

Самое простое — попросить кого-нибудь: «Эй, выбери случайное число от одного до десяти!». Человек отвечает: «Семь!». Отлично! Теперь у вас есть число. Однако вы начинаете задаваться вопросом, является ли оно равномерно распределённым?

Поэтому вы решили спросить ещё несколько человек. Вы продолжаете их спрашивать и считать их ответы, округляя дробные числа и игнорируя тех, кто думает, что диапазон от 1 до 10 включает 0. В конце концов вы начинаете видеть, что распределение вообще не равномерное:

Данные с Reddit

Вы хлопаете себя по лбу. Ну конечно, оно не будет случайным. В конце концов, нельзя доверять людям.

Итак, что делать?

Вот бы найти какую-то функцию, которая преобразует распределение «человеческого ГСЧ» в равномерное распределение…

Интуиция тут относительно проста. Нужно всего лишь взять массу распределения оттуда, где она выше 10%, и переместить туда, где она меньше 10%. Так, чтобы все столбцы на графике были одного уровня:

По идее, такая функция должна существовать. Фактически, должно быть много различных функций (для перестановки). В крайнем случае, можно «разрезать» каждый столбец на бесконечно малые блоки и построить распределение любой формы (как кирпичики Lego).

Конечно, такой экстремальный пример немного громоздок. В идеале мы хотим сохранить как можно больше исходного распределения (т. е. сделать как можно меньше измельчений и перемещений).

Как найти такую функцию?

Ну, наше объяснение выше звучит очень похоже на линейное программирование. Из Википедии:

Линейное программирование (LP, также именуется линейной оптимизацией) — метод достижения наилучшего результата… в математической модели, требования которой представлены линейными отношениями… Стандартная форма представляет собой обычную и наиболее интуитивную форму описания задачи линейного программирования. Она состоит из трёх частей:

• Линейная функция, которую необходимо максимизировать
• Проблемные ограничения следующей формы
• Неотрицательные переменные

Аналогично можно сформулировать и проблему перераспределения.

Представление проблемы

У нас есть набор переменных , каждая из которых кодирует долю вероятности, перераспределённую от целого числа (от 1 до 10) к целому числу (от 1 до 10). Поэтому, если , то нам нужно перенести 20% ответов от семёрки к единице.

Мы хотим ограничить эти переменные таким образом, чтобы все перераспределённые вероятности суммировались в 10%. Другими словами, для каждого от 1 до 10:

Можем представить эти ограничения в виде списка массивов в R. Позже свяжем их в матрицу.

Мы также должны убедиться, что сохраняется вся масса вероятностей из исходного распределения. Так что для каждого в диапазоне от 1 до 10:

Как уже говорилось, мы хотим максимизировать сохранение исходного распределения. Это наша цель (objective):

Затем передаём проблему солверу, например, пакету lpSolve в R, объединив созданные ограничения в одну матрицу:

Возвращается следующее перераспределение:

Отлично! Теперь у нас есть функция перераспределения. Давайте поближе посмотрим, как именно движется масса:

Эта диаграмма говорит, что примерно в 8% случаев, когда кто-то называет восемь в качестве случайного числа, вам нужно воспринимать ответ как единицу. В остальных 92% случаев он остаётся восьмёркой.

Было бы довольно просто решить задачу, если бы у нас был доступ к генератору равномерно распределённых случайных чисел (от 0 до 1). Но у нас только комната, полная людей. К счастью, если вы готовы примириться с несколькими небольшими неточностями, то из людей можно сделать довольно хороший ГСЧ, не спрашивая более двух раз.

Возвращаясь к нашему исходному распределению, у нас есть следующие вероятности для каждого числа, которые можно использовать для повторного назначения любой вероятности, если необходимо.

Например, когда кто-то даёт нам восемь в качестве случайного числа, нужно определить, должна ли эта восьмёрка стать единицей или нет (вероятность 8%). Если мы спросим другого человека о случайном числе, то с вероятностью 8,5% он ответит «два». Так что если это второе число равно 2, мы знаем, что должны вернуть 1 как равномерно распределённое случайное число.

Распространив эту логику на все числа, получаем следующий алгоритм:

• Спросить у человека случайное число, .
• или :
  • Ваше случайное число
• Если :
  • Спросить у другого человека случайное число ()
  • Если (12.2%):
    • Ваше случайное число 2
  • Если (1.9%):
    • Ваше случайное число 4
  • В противном случае, ваше случайное число 5
• Если :
  • Спросить у другого человека случайное число ()
  • Если или (20.7%):
    • Ваше случайное число 1
  • Если или (16.2%):
    • Ваше случайное число 9
  • Если (28.1%):
    • Ваше случайное число 10
  • В противном случае, ваше случайное число 7
• Если :
  • Спросить у другого человека случайное число ()
  • Если (8.5%):
    • Ваше случайное число 1
  • В противном случае, ваше случайное число 8

Источник

Цикл for в Python

Простой перебор

Цикл в любом языке программирования — это многократное выполнение одного и то же действия. Цикл for проходится по данной последо­ватель­ности элементов. Он состоит из двух компонент: переменной (переменных) цикла и итерируемой (перебираемой) последовательности. Приведу пример:

for i in ‘one’ , ‘two’ , ‘three’ :
print (i)
# one
# two
# three

Приведу еще несколько примеров:

for i in ‘1’ , ‘hello’ , 2 , 1990 , True, False:
print (i)
for j in ‘orange’ , ‘red’ , ‘purple’ :
print (j)
for k in ‘first’ , ‘last’ :
print (k)

Функция range()

Теперь пришло время познакомиться с встроенной в Python функцией range(). «range» переводится как «диапазон». Она может принимать один, два или три аргумента. Если задан только один, то генерируются числа от 0 до указанного числа, не включая его. Если заданы два, то числа генерируются от первого до второго, не включая его. Если заданы три, то третье число – это шаг. Рассмотрим случай с одним аргументом:

for number in range ( 5 ):
print (number)
for number in 0 , 1 , 2 , 3 , 4 :
print (number)

Напечатаются числа от 0 до 4. Это связано с тем, что функция range с одним аргументом генерирует диапазон от 0 до n-1, где n — это переданный аргумент.

Передадим в функцию два аргумента: 5 и 10. В этом случае range cгенерирует последовательность чисел от 5 до 9.

for el in range ( 5 , 10 , 2 ):
print (el)

Если передать в range три аргумента: 5, 10, 2, то мы получим последовательность от 5 до 10 с шагом в 2

for el in range ( 5 , 10 ):
print (el)

Перебор строк и функция len()

С помошью цикла for мы можем перебрать любую последовательность, например, строку:

for letter in ‘hello’ :
print (letter)
for l in ‘python’ :
print (l)

Любая последовательность имеет длину, это означает, что мы можем ее посчитать

Примеры решения задач

1. Посчитать сумму чисел от 0 до number

number = int ( input ())
summa = 0
for i in range (number +1 ):
# summa = summa + i
summa += i
print (summa)

2. Посчитать сумму четных чисел от 0 до number

number = int ( input ())
summa = 0
for i in range (number +1 ):
if i % 2 == 0 :
# summa = summa + i
summa += i
print (summa)

3. Посчитать произведение чисел от 1 до number

number = int ( input ())
multi = 1
for i in range ( 1 , number +1 ):
multi *= i
print (multi)

Решение задач

1. Вывести числа от 0 до 10.

2. Вывести числа от 0 до n, где n — это случайное число или число, введенное с клавиатуры

3. Вывести нечетные числа в диапазона от 0 до n (диапазон — это последовательность чисел от 0 до n)

4. Вывести четные числа из диапазона от 0 до n.

5. Вывести числа, делящиеся на три без остатка, в диапазоне от 0 до n.

6. Вывести числа, делящиеся на три или на семь без остатка, в диапазоне от 0 до n.

7. Найти сумму всех чисел от 1 до n.

7. Найти сумму четных чисел от 1 до n.

8. Даны два целых числа a и b a . Найти сумму всех целых чисел от a до b включительно.

9. Найти сумму чисел от 1 до n, делящихся на 3 .

10. Дано целое число n. Найти сумму 1 + 1/2 + 1/3 + . + 1/n

11. Дано целое число n. Найти сумму 1 + 2 + 4 + 8 + 16 + . + 2**n
где 2**n — это 2*2*2*. *2 раз. Таким образом, 2**4 = 2*2*2*2. Операция ** называется операцией возведения в степень.

12. Дано целое число n. Найти сумму: 1.1 + 1.2 + 1.3 + . + (1 + 0.1*n)

13. Дано целое число n. Найти значение выражения 1.1 − 1.2 + 1.3 − . (N слагаемых, знаки чередуются).

14. Дано целое число n. Найти квадрат данного числа, используя для его вычисления следующую формулу: n**2 = 1 + 3 + 5 + . + (2*N − 1) После добавления к сумме каждого слагаемого выводить текущее значение суммы

15. Дано вещественное число A и целое число N (> 0). Найти A в степени N: A**N = A * A * . * A (числа A перемножаются N раз). Операцию ** не использовать.

16. По данному натуральному n ≤ 30 выведите лесенку из n ступенек, i-я ступенька состоит из чисел от 1 до i без пробелов. Посмотрите статью про ввод и вывод данных.

17. Дано целое число n. Найти сумму 1**1 + 2**2 + . + n**n .

Источник