Найти площадь и периметр прямоугольного треугольника по двум заданным катетам



бет26/34
Дата05.01.2022
өлшемі186,75 Kb.
#129167
1   ...   22   23   24   25   26   27   28   29   ...   34
Байланысты:
шпор

Исходный код на Python

from random import randint

 

# Создание списка,



# его сортировка по возрастанию

# и вывод на экран

a = []


for i in range(10):

a.append(randint(1, 50))

a.sort()

print(a)

 

# искомое число

value = int(input())

 

mid = len(a) // 2



low = 0

high = len(a) - 1

 

while a[mid] != value and low <= high:

if value > a[mid]:

low = mid + 1



else:

high = mid - 1

mid = (low + high) // 2

 

if low > high:



print("No value")

else:

print("ID =", mid)

Примеры выполнения:

[6, 17, 21, 27, 32, 35, 35, 36, 37, 48]

27

ID = 3



[4, 5, 12, 13, 13, 18, 22, 26, 30, 35]

28

No value



Решето Эратосфена – это алгоритм нахождения простых чисел до заданного натурального числа путем постепенного отсеивания составных чисел. Образно говоря, через решето Эратосфена в процессе его тряски проскакивают составные числа, а простые остаются в решете.

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число - это 2, второе простое число - это 3. Теперь начнем рассуждать:



  1. Все четные числа, кроме двойки, - составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.

  2. Все числа кратные трем, кроме самой тройки, - составные, так как делятся не только на самих себя и единицу, а также еще на 3.

  3. Число 4 уже выбыло из игры, так как делится на 2.

  4. Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.

  5. Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

Последний пункт вытекает из того, что сложные числа всегда можно представить как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.

Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа n в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.

Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до n. Здесь важнее индексы, чем значения элементов. Значениями может быть True, обозначающее простое число, и False, обозначающее сложное число.

В данном примере реализации алгоритма Эратосфена список заполняется числами от 0 до n включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:

n = int(input())

 

# список заполняется значениями от 0 до n

a = []


for i in range(n + 1):

a.append(i)

 

# Вторым элементом является единица,

# которую не считают простым числом

# забиваем ее нулем.

a[1] = 0


 

# начинаем с 3-го элемента

i = 2


while i <= n:

# Если значение ячейки до этого

# не было обнулено,

# в этой ячейке содержится

# простое число.



Достарыңызбен бөлісу:
1   ...   22   23   24   25   26   27   28   29   ...   34




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет