LINUX.ORG.RU
решено Форум — Development  

Книжка по алгоритмам с задачами для школьников

 


5

2

Была такая pdf'ка по алгоритмам для школьников из какой-то школы с математическим уклоном, там задачи в основном, очень известная, никак не могу её нагуглить. Может кто-то понимает, о чём идёт речь?

← Как создать исполняемый файл, работающий и на 32 , и на 64 бит?
Вызов программы с выводом в виде строки →

Что вы за люди, где вы были 10 лет назад?

anonymous
()
Ответ на: комментарий от bormant

Здрасть, кто-нибудь может объяснить почему вот этот код работает: 

func solution(a, b int) (x, y int) {
	xA, yA := 1, 0
	xB, yB := 0, 1
	for a != 0 && b != 0 {
		if a > b {
			a -= b
			xA -= xB
			yA -= yB
			continue
		}
		b -= a
		xB -= xA
		yB -= yA
	}
	if a != 0 {
		return xA, yA
	}
	return xB, yB
}
Задача - найти такие целые коэффиценты x и y, чтобы xa + yb = НОД(a, b).

Понятно, что это стандартный алгоритм Евклида. Понятно, что имеется 2 пары возможных коэффициентов по умолчанию: x=1, y=0, если a и есть НОД; x=0, y=1, если b - НОД. А дальше, почему в конечном счёте получаются правильные коэффициенты?

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Как создать исполняемый файл, работающий и на 32 , и на 64 бит?
Development
Вызов программы с выводом в виде строки →