Алгоритм Евклида
Алгоритм Евклида позволяет найти наибольший общий делитель (НОД) двух натуральных чисел.
Алгоритм Евклида для натуральных чисел: заменять бóльшее из двух заданных чисел на их разность до тех пор, пока они не станут равны. Полученное число и есть их НОД.
Этот вариант алгоритма работает довольно медленно, если одно из чисел значительно меньше другого, например, для па-ры чисел 2 и 2020. Значительно быстрее выполняется улучшен-ный (модифицированный) алгоритм Евклида.
Модифицированный алгоритм Евклида для натуральных чисел: заменять бóльшее из двух заданных чисел на остаток от деления бóльшего на меньшее, пока этот остаток не станет ра-вен нулю. Тогда второе число и есть их НОД.
Мы видим, что здесь тоже нужно выполнять некоторые операции несколько раз, причём сколько раз – заранее неиз-вестно. Но нас выручит цикл с условием, ведь мы знаем, когда нужно остановиться – когда какое-нибудь из двух чисел станет равно нулю.
57 http://kpolyakov.spb.ru![](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAAnACYDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD3DU9TttJs2ublsKOAByWPoB3Ned6n4z1S+dlgk+yw9lj+9j3b1+mKTxlqbX+tvCG/c23yKO27+I/XPH4CudHUfWvBxmMnKfJB2RxVarbsi8ms6oj7l1G6z15lY/oTzXR6N45uIpFh1P8AexHjzVGGX6gcEfr9a1vGtnaweHy8VvFG3mLyqAH+VecVlUlWwlRJSuTJypS3PcYpEniWSNgyMMhhyCKK4zwFqjSW8+nStnyvnjz/AHSeR+ePzor2qOIhUgpdzshNSjc5G/AXxDdCXGPtTbs9MbjnNd+J/COB8umZ/wCuaf4VzfjjSGtdSN/GuYLjG4jorgY/UDP1zXKDqPrXje0eGqSi43uzk5vZyaaue0am1gtoTqPkfZ8j/XAFc9utcj4kl8Otokw08WIucrt8pFDY3DPQemateMtSsbvQDHb3lvLJ5inakqsfyBrzuunHYpJ8iSd0XWqW0SOk8FLI2sTeX1Fuf/Qloro/BGjvZ2El5Ou2W4xtBHRB/j1/Kiqw+DbppsunTfKjp7m2hvLd4J41kjcbWVuhrhdT8ATJIz6dOroefLlOCPoQOfxooruxFCnVjeSNZ04y3MtPBmtM+028aj+8ZVx+hJ/Suj0XwNDaSLcahIs7ryI1HyD656/TgUUVz4fBUk7tXM4UYpnZAYFFFFeibn//2Q==) ![](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAA2ADYDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD2bXPEFpoUCSXAZnkyEjQZJx1/DkVhf8LHsv8AnxuPzX/Gs/4kf8flj/1zb+YriOpr3MFl9GpRU57s+VzLN8RRxMqdPZHo/wDwsey/58bj81/xo/4WRZf8+Nx+a/415xxToopJ5liiQvI5wFXnP4V1PLMMldpnCs7xrdk9fQ9E/wCFj2P/AD43H5r/AI0q/EexP3rK5x6jaf61iWGnpZ3MWmW9lbX+pOQ1y0wDxwL6ex9/w5qv4n0SztZJLnTJVeGOQR3ESnPkueR+B6ex49hyRw+ElU5LPXZ3O+eMzCNL2nMnbfT+vmem2N7BqNnHd27BopBlT/nvRWJ4F58LQ56eY/8AM0V5FeKp1JQXRn0eFqe2oxqSWrSMD4k/8ftj/wBc2/mK4eu4+JP/AB+2H/XNv5iuJjjeaRIo0Z3Y4VVGSSegAr6bL3bDRbPh83TeNml/WgsUUk8yxRIzu5CqqjJJPQCut0/TZrCcafp4WTWJV/fz9VtUPYH+9/kUunaXNp062Nmqya1KuZJeClmh9/7xH8+OvOiWFkkmiaJIBNgtf6g5/wBX65Pr14zx+ZHNicT7R8sdv619PzOzBYNUlz1N/wCtF59+w12WxR9D0Nx5wG6+v2P+r9ST69e/H1yRzWq6lbrbf2VpY/0NTukmYfNcP6n0GaNV1aEW40vSwUsUOXc/enbuzH09B9PYDF71thcN9uf9ev6Loc+Nxt706e39aL9X1PV/Af8AyK8X/XR/50UeA/8AkV4v+uj/AM6K8DFfx5+rPrsB/utP0Rz/AMSf+Pyx/wCubfzFZ3hx7SwsZb+dzFNNL9miuNobyCVJLAHr2H+TWj8SP+P2w/65t/MVk2Wv2Nv4fXS59M+1AuXctJsGc8EEAkHGB2r2KUZSwcYxTeup83iZQhmM5zdrd/RHTyQmwQ6TpTlDInnXmpSH7qnPOe5POOePzI5LVtWgMH9maUpjsFOXfPzTt/eY9cen/wCoCPU/EM+oWcNjHEtvZRAAQo5bOOmSeSB2H/1sZHIrbC4Rx96p/Xr/AFocuNzBT9yjt3/Rf1qJRRRXonjnrHgP/kV4v+uj/wA6KTwLx4Whz/z0f+dFfIYr+PP1Z+jYD/dqfoi/regWmvW6Jc7lZDlJExuXP1HQ8Zrnz8ObL/n9uPyX/Ciiijia1ONoysRicHQqz5pxTY7/AIVvZf8AP9cfkv8AhR/wriy/5/rj8l/wooq/r2I/nM/7Lwn/AD7Qf8K3sv8An+uPyX/ChfhxYBgWvbllHb5Rn9KKKf13EfzMP7Mwn/PtHV2VnDp9pHbW6bY0GFFFFFcUm27s9OEYqKSR/9k=)
![](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAA2ADYDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD2bXPEFpoUCSXAZnkyEjQZJx1/DkVhf8LHsv8AnxuPzX/Gs/4kf8flj/1zb+YriOpr3MFl9GpRU57s+VzLN8RRxMqdPZHo/wDwsey/58bj81/xo/4WRZf8+Nx+a/415xxToopJ5liiQvI5wFXnP4V1PLMMldpnCs7xrdk9fQ9E/wCFj2P/AD43H5r/AI0q/EexP3rK5x6jaf61iWGnpZ3MWmW9lbX+pOQ1y0wDxwL6ex9/w5qv4n0SztZJLnTJVeGOQR3ESnPkueR+B6ex49hyRw+ElU5LPXZ3O+eMzCNL2nMnbfT+vmem2N7BqNnHd27BopBlT/nvRWJ4F58LQ56eY/8AM0V5FeKp1JQXRn0eFqe2oxqSWrSMD4k/8ftj/wBc2/mK4eu4+JP/AB+2H/XNv5iuJjjeaRIo0Z3Y4VVGSSegAr6bL3bDRbPh83TeNml/WgsUUk8yxRIzu5CqqjJJPQCut0/TZrCcafp4WTWJV/fz9VtUPYH+9/kUunaXNp062Nmqya1KuZJeClmh9/7xH8+OvOiWFkkmiaJIBNgtf6g5/wBX65Pr14zx+ZHNicT7R8sdv619PzOzBYNUlz1N/wCtF59+w12WxR9D0Nx5wG6+v2P+r9ST69e/H1yRzWq6lbrbf2VpY/0NTukmYfNcP6n0GaNV1aEW40vSwUsUOXc/enbuzH09B9PYDF71thcN9uf9ev6Loc+Nxt706e39aL9X1PV/Af8AyK8X/XR/50UeA/8AkV4v+uj/AM6K8DFfx5+rPrsB/utP0Rz/AMSf+Pyx/wCubfzFZ3hx7SwsZb+dzFNNL9miuNobyCVJLAHr2H+TWj8SP+P2w/65t/MVk2Wv2Nv4fXS59M+1AuXctJsGc8EEAkHGB2r2KUZSwcYxTeup83iZQhmM5zdrd/RHTyQmwQ6TpTlDInnXmpSH7qnPOe5POOePzI5LVtWgMH9maUpjsFOXfPzTt/eY9cen/wCoCPU/EM+oWcNjHEtvZRAAQo5bOOmSeSB2H/1sZHIrbC4Rx96p/Xr/AFocuNzBT9yjt3/Rf1qJRRRXonjnrHgP/kV4v+uj/wA6KTwLx4Whz/z0f+dFfIYr+PP1Z+jYD/dqfoi/regWmvW6Jc7lZDlJExuXP1HQ8Zrnz8ObL/n9uPyX/Ciiijia1ONoysRicHQqz5pxTY7/AIVvZf8AP9cfkv8AhR/wriy/5/rj8l/wooq/r2I/nM/7Lwn/AD7Qf8K3sv8An+uPyX/ChfhxYBgWvbllHb5Rn9KKKf13EfzMP7Mwn/PtHV2VnDp9pHbW6bY0GFFFFFcUm27s9OEYqKSR/9k=) ![](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0aHBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCAA2ADYDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD2bXPEFpoUCSXAZnkyEjQZJx1/DkVhf8LHsv8AnxuPzX/Gs/4kf8flj/1zb+YriOpr3MFl9GpRU57s+VzLN8RRxMqdPZHo/wDwsey/58bj81/xo/4WRZf8+Nx+a/415xxToopJ5liiQvI5wFXnP4V1PLMMldpnCs7xrdk9fQ9E/wCFj2P/AD43H5r/AI0q/EexP3rK5x6jaf61iWGnpZ3MWmW9lbX+pOQ1y0wDxwL6ex9/w5qv4n0SztZJLnTJVeGOQR3ESnPkueR+B6ex49hyRw+ElU5LPXZ3O+eMzCNL2nMnbfT+vmem2N7BqNnHd27BopBlT/nvRWJ4F58LQ56eY/8AM0V5FeKp1JQXRn0eFqe2oxqSWrSMD4k/8ftj/wBc2/mK4eu4+JP/AB+2H/XNv5iuJjjeaRIo0Z3Y4VVGSSegAr6bL3bDRbPh83TeNml/WgsUUk8yxRIzu5CqqjJJPQCut0/TZrCcafp4WTWJV/fz9VtUPYH+9/kUunaXNp062Nmqya1KuZJeClmh9/7xH8+OvOiWFkkmiaJIBNgtf6g5/wBX65Pr14zx+ZHNicT7R8sdv619PzOzBYNUlz1N/wCtF59+w12WxR9D0Nx5wG6+v2P+r9ST69e/H1yRzWq6lbrbf2VpY/0NTukmYfNcP6n0GaNV1aEW40vSwUsUOXc/enbuzH09B9PYDF71thcN9uf9ev6Loc+Nxt706e39aL9X1PV/Af8AyK8X/XR/50UeA/8AkV4v+uj/AM6K8DFfx5+rPrsB/utP0Rz/AMSf+Pyx/wCubfzFZ3hx7SwsZb+dzFNNL9miuNobyCVJLAHr2H+TWj8SP+P2w/65t/MVk2Wv2Nv4fXS59M+1AuXctJsGc8EEAkHGB2r2KUZSwcYxTeup83iZQhmM5zdrd/RHTyQmwQ6TpTlDInnXmpSH7qnPOe5POOePzI5LVtWgMH9maUpjsFOXfPzTt/eY9cen/wCoCPU/EM+oWcNjHEtvZRAAQo5bOOmSeSB2H/1sZHIrbC4Rx96p/Xr/AFocuNzBT9yjt3/Rf1qJRRRXonjnrHgP/kV4v+uj/wA6KTwLx4Whz/z0f+dFfIYr+PP1Z+jYD/dqfoi/regWmvW6Jc7lZDlJExuXP1HQ8Zrnz8ObL/n9uPyX/Ciiijia1ONoysRicHQqz5pxTY7/AIVvZf8AP9cfkv8AhR/wriy/5/rj8l/wooq/r2I/nM/7Lwn/AD7Qf8K3sv8An+uPyX/ChfhxYBgWvbllHb5Rn9KKKf13EfzMP7Mwn/PtHV2VnDp9pHbW6bY0GFFFFFcUm27s9OEYqKSR/9k=) 05.04.2019 Информатика, 8 класс К.Ю. Поляков, Е.А. Еремин
Запишите условие, которое означает «одно из значений переменных a или b равно нулю». После этого запишите обратное условие.
Теперь мы готовы записать цикл:
while a != 0 and b != 0:
if a > b:
a = a % b else:
b = b % a
Остаётся вывести результат – ненулевое значение пере-менной a или b.
Запишите условный оператор, который выводит результат, проверяя одну из переменных на равенство нулю.
Из двух переменных, a и b, одна (неизвестно какая) равна нулю, а вторая – не ноль. Запишите арифметическое выражение, которое всегда равно второй (ненулевой) переменной.
Количество итераций такого цикла заранее неизвестно и зависит от исходных данных. Дополним программу так, чтобы она считала ещё и количество сделанных итераций. Для этого нужно ввести переменную-счётчик целого типа. Перед началом цикла счётчик обнуляется (в него записывается ноль), и после каждой итерации значение счётчика увеличивается на едини-цу:
count = 0
while a != 0 and b != 0:
...
count += 1 print( a + b )
print( "Шагов:", count )
Вместо многоточия нужно вставить условный оператор, как и в предыдущем варианте программы. Обратите внимание, что
58 http://kpolyakov.spb.ru
05.04.2019 Информатика, 8 класс К.Ю. Поляков, Е.А. Еремин
оператор, увеличивающий значение счётчика, записывается с отступом – он находится в теле цикла.
Достарыңызбен бөлісу: |