Общее решение диофантова уравнения
Написал программу для решения диофантова уравнения вида 45x-128y=177. Имеется два вопроса:
- а как сделать так, чтобы выводилось общее решение диофантова уравнения в виде формулы, зависящей от параметра?
- можно ли тут реализовать вывод данных, полученных на промежуточных этапах решения задачи, а не только конечный результат?
def nod(m, n): return m if n == 0 else nod(n, m % n) a = int(input('Введите коэффициент a: ')) b = int(input('Введите коэффициент b: ')) c = int(input('Введите коэффициент c: ')) print() assert c != 0 nod_ab = nod(abs(a), abs(b)) if c % nod_ab: print('Решения нет') else: a //= nod_ab b //= nod_ab c //= nod_ab for i in range(abs(a)): if (c - b * i) % a == 0: y = i x = (c - b * y) // a if x < 0: x += b y -= a print('x = ', x, 'y = ', y, '\n', 'Проверка: ', ((a*x)+(b*y)), ' = ', c, ' - Левая часть равна правой части уравнения') break else: print('Решения нет') Ответы (1 шт):
уравнение вида ax + by = c в случае, если известно хотя бы одно решение (x0, y0) имеет следующие решения:
x = x0 + k * b / НОД(a, b) y = y0 + k * a / НОД(a, b) т.е. задача сводится к нахождению хотя бы одного решения и вычислению gcd(a, b)
import math def gcd(a, b): if a == 0: return (b, 0, 1) res = gcd(b % a, a) x = res[2] - (b // a) * res[1] y = res[1] return (res[0], x, y) # найти любое решение def find_solution (a, b, c): g, x0, y0 = gcd(abs(a), abs(b)) if c % g != 0: return (False, 0, 0) x0 *= c // g y0 *= c // g if a < 0: x0 *= -1 if b < 0: y0 *= -1 return (True, x0, y0) # Определить любое решение a, b, c = 45, -128, 177 res = find_solution(45, -128, 177) if res[0] is True: print(f"x = + k * ") print(f"y = + k * ") else: print("Решений нет") вывод отрицательных значений надо только красиво оформить 🙂
Диофантово уравнение
Здравствуйте, пожалуйста помогите сделать мой код работающим верно.
Даны натуральные числа a, b, c. Если уравнение ax+by=c
имеет решения в целых числах, то выберите то решение, в котором число x
имеет наименьшее неотрицательное значение, и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите −1.
Входные данные — натуральные числа a, b и c. Числа заданы на одной строке через пробел и не превышают 10 9 .
Примеры:
Ввод:
1 2 3
Вывод:
1 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
def gcd_ext(a, b): if b == 0: return a, 1, 0 d, x, y = gcd_ext(b, a % b) x, y = y, x - (a // b) * y return d, x, y inp = [int(x) for x in input().split()] comp = gcd_ext(inp[0], inp[1]) x_y = [] for t in range(10): x = ((inp[2] // comp[0]) * comp[1]) - t * (inp[1] // comp[0]) y = ((inp[2] // comp[0]) * comp[2]) + t * (inp[0] // comp[0]) x_y.append([x, y]) if x >= 0 else None if x != []: print(*sorted(x_y, key = lambda x: x[0])[0]) else: print(1)
Диофантово уравнение
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то.
Диофантово уравнение — 2
Диофантово уравнение — 2 Даны числа a,b,c,d,e. Подсчитайте количество таких целых чисел от 0 до.
Диофантово уравнение
Недавно начал изучать Python. Первый язык программирования (не считая Pascal). Встретилась задача.
Диофантово уравнение
Здравствуйте! Решаю следующую задачу: Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет.
Линейное Диофантово уравнение
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то.
Линейное Диофантово уравнение
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.
Диофантово уравнение
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то.
Диофантово уравнение
Здравствуйте! Решаю следующую задачу: Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет.
Диофантово уравнение — 2
Диофантово уравнение — 2 Даны числа a,b,c,d,e. Подсчитайте количество таких целых чисел от 0 до.
Диофантово уравнение
Здравствуйте, пожалуйста помогите сделать мой код работающим верно. Даны натуральные числа a.
Есть такая штуковина, называется "Обобщенный алгоритм Евклида", который позволяет подобрать решение уравнения ax + by = НОД(a, b)
Сообщение было отмечено ildwine как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
#!/usr/bin/env python3 def nod(m, n): return m if n == 0 else nod(n, m % n) a = int(input("A = ")) b = int(input("B = ")) c = int(input("C = ")) assert c != 0 nodAB = nod(abs(a), abs(b)) if c % nodAB: print("Impossible") else: a //= nodAB b //= nodAB c //= nodAB for k in range(abs(a)): if ( c - b * k ) % a == 0: y = k x = ( c - b * y ) // a print("X =", x, "Y =", y) break else: print("Shit happens!")
Сообщение от S E R Nag 
Сообщение от easybudda
Сообщение было отмечено ildwine как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
#!/usr/bin/env python3 def nod(m, n): return m if n == 0 else nod(n, m % n) a = int(input("A = ")) b = int(input("B = ")) c = int(input("C = ")) assert c != 0 nodAB = nod(abs(a), abs(b)) if c % nodAB: print("Impossible") else: a //= nodAB b //= nodAB c //= nodAB for k in range(abs(a)): if ( c - b * k ) % a == 0: y = k x = ( c - b * y ) // a if x 0: x += b y -= a print("X =", x, "Y =", y) break else: print("Shit happens!")
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
def gcd(a, b): while a != 0 and b != 0: if a b: b = b % a else: a = a % b return a + b def qwer(a, b): x = 1 x1 = 0 y = 0 y1 = 1 while b != 0: q = a // b r = a % b x2 = x - q * x1 y2 = y - q * y1 a, b = b, r x, x1 = x1, x2 y, y1 = y1, y2 return str(a), str(x), str(y) a, b, c = list(map(int, input().split())) x, y = 0, 0 gcds = 0 if c % gcd(a, b) != 0: print('Impossible') else: gcds, x, y = map(int, qwer(a, b)) x *= c // gcds y *= c // gcds q = x // (b // gcds) x %= b // gcds y += a // gcds * q print(x, y)
Диофантово уравнение питон
Почему-то частичное решение, неправильный ответ
Даны числа a, b, c, d, e. Подсчитайте количество таких целых чисел от 0 до 1000, которые являются корнями уравнения (ax3+bx2+cx+d)/(x-e)=0, и выведите их количество.
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
sum=0
for x in range(1001):
m= (a * x*x*x) + (b * (x*x) + c * x + d)
if((x-e) != 0):
if (m//(x-e)==0):
sum+=1
print(sum)
count, a, b, c, d, e = 0, *(int(input()) for _ in range(5))
for x in range(1001):
if x - e and (a * x ** 3 + b * x ** 2 + c * x + d) / (x - e) == 0:
count += 1
print(count)
1) Решение должно быть в целых числах, значит, на (x - e) должно делиться без остатка.
2) Я вообще не понимаю этого прикола, на кой ляд вы все ищете частное с (x - e)? Проверить числитель недостаточно?
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
count = 0
for x in range(1001):
if x != e and (a*x**3 + b*x**2 + c*x + d) % (x-e) == 0:
count += 1
print(count)
Основные поправки:
- Исправлены отступы после каждой строки кода (2 или 4 пробела) для повышения читаемости.
- Исправлены имена переменных на более подходящие (sum -> count).
- Добавлены скобки вокруг математических выражений для явности порядка операций.
- Добавлены проверки на неравенство x и e, чтобы не было деления на ноль.
- Исправлено условие проверки на равенство нулю для потенциальных корней уравнения (с помощью операции модуля).
Ваш прошел 4 теста
Диофантово уравнение
Недавно начал изучать Python. Первый язык программирования (не считая Pascal). Встретилась задача:
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.
Написал с помощью интернета такую программу:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
import sys def gcd(z, v): while z != 0 and v != 0: if z v: v = v % z else: l = z % v return z + v def qwer(z, v): x = 1 x1 = 0 y = 0 y1 = 1 while v != 0: q = z // v r = z % v x2 = x - q * x1 y2 = y - q * y1 l, v = v, r x, x1 = x1, x2 y, y1 = y1, y2 return str(z), str(x), str(y) a = int(input()) b = int(input()) c = int(input()) if a == b == 0: if c == 0: print(0,0) sys.exit() else: print('Impossible') sys.exit() if a == 0: print(c // b, 0) sys.exit() if b == 0: print(c // a,0) sys.exit() if c == 0: print(0,0) sys.exit() x, y = 0, 0 gcds = 0 if c % gcd(a, b) != 0: print('Impossible') else: gcds, x, y = map(int, qwer(a, b)) x *= c // gcds y *= c // gcds q = x // (b // gcds) x %= b // gcds y += a // gcds * q print(x,y)
И у меня в PyCharm всё работает. А компилятор сайта почему-то выдаёт ошибку. В чём проблема?
p.s Если будут предложения по оптимизации - буду рад