Написать программу для машины Поста, которая бы находила наименьший общий делитель двух чисел

@Tukan4ik · Регистрация: 16.09.2019

Студворк — интернет-сервис помощи студентам

Найти наименьший общий делитель двух чисел, находящихся на ленте
машины Поста. Между этими числами находится произвольное количество
пустых секций. Каретка находится над левой меткой левого числа.

@Sindbad_M · 28.10.2019, 01:02

1. Алгоритмом Евклида найти наибольший общий делитель НОД
2. Перебирая числа от 2 до найденного НОД найти наименьший делитель для НОД, это и есть искомый наименьший общий делитель.

@kabenyuk · 28.10.2019, 13:43

Сообщение от Tukan4ik

наименьший общий делитель двух чисел

равен 1. Тут и искать ничего не надо.

@Tukan4ik · 28.10.2019, 15:22 **[ТС]**

1. Алгоритмом Евклида найти наибольший общий делитель НОД
2. Перебирая числа от 2 до найденного НОД найти наименьший делитель для НОД, это и есть искомый наименьший общий делитель.

Это понятно, но не понятно как это в машину занести xD

@Sindbad_M · 28.10.2019, 15:51

А что умеете в машину заносить? Например, можете организовать вычитание из левого числа правого?

@Tukan4ik · 28.10.2019, 18:32 **[ТС]**

Ну это думаю смогу организовать

@Sindbad_M · 28.10.2019, 21:28

Сообщение от Tukan4ik

Ну это думаю смогу организовать

Тогда алгоритм Евклида у вас в кармане, т.к. сводится к цепочке вычитаний:
- вычитаете из большего числа меньшее до тех пор, пока не получите результат меньший меньшего числа
- принимаете результат за новое меньшее число, а старое меньшее за новое большее и переходите к первому пункту
- когда на каком-то шаге получите ноль, то число предыдущего шага и есть НОД

@Tukan4ik 0 / 0 / 0 Регистрация: 16.09.2019 Сообщений: 9
		1
	Написать программу для машины Поста, которая бы находила наименьший общий делитель двух чисел 27.10.2019, 19:26. Показов 2816. Ответов 6 Метки нет (Все метки) Найти наименьший общий делитель двух чисел, находящихся на ленте машины Поста. Между этими числами находится произвольное количество пустых секций. Каретка находится над левой меткой левого числа. 0

@Sindbad_M 429 / 363 / 109 Регистрация: 23.05.2016 Сообщений: 1,484
	28.10.2019, 01:02	2
	1. Алгоритмом Евклида найти наибольший общий делитель НОД 2. Перебирая числа от 2 до найденного НОД найти наименьший делитель для НОД, это и есть искомый наименьший общий делитель. 0

@kabenyuk $Эксперт по математике/физике$ 3973 / 2952 / 895 Регистрация: 19.11.2012 Сообщений: 6,064
	28.10.2019, 13:43	3
	Сообщение от Tukan4ik наименьший общий делитель двух чисел равен 1. Тут и искать ничего не надо. 0

@Tukan4ik 0 / 0 / 0 Регистрация: 16.09.2019 Сообщений: 9
	28.10.2019, 15:22 [ТС]	4
	1. Алгоритмом Евклида найти наибольший общий делитель НОД 2. Перебирая числа от 2 до найденного НОД найти наименьший делитель для НОД, это и есть искомый наименьший общий делитель. Это понятно, но не понятно как это в машину занести xD 0

@Sindbad_M 429 / 363 / 109 Регистрация: 23.05.2016 Сообщений: 1,484
	28.10.2019, 15:51	5
	А что умеете в машину заносить? Например, можете организовать вычитание из левого числа правого? 0

@Tukan4ik 0 / 0 / 0 Регистрация: 16.09.2019 Сообщений: 9
	28.10.2019, 18:32 [ТС]	6
	Ну это думаю смогу организовать 0

@Sindbad_M 429 / 363 / 109 Регистрация: 23.05.2016 Сообщений: 1,484
	28.10.2019, 21:28	7
	Сообщение от Tukan4ik Ну это думаю смогу организовать Тогда алгоритм Евклида у вас в кармане, т.к. сводится к цепочке вычитаний: - вычитаете из большего числа меньшее до тех пор, пока не получите результат меньший меньшего числа - принимаете результат за новое меньшее число, а старое меньшее за новое большее и переходите к первому пункту - когда на каком-то шаге получите ноль, то число предыдущего шага и есть НОД 0

Опции темы