#include <stdio.h>
void main()
{
const ArrLength = 100;
int n, m, cn, cm, k, tmp, i, g, x;
int InArr[ArrLength];
int ImArr[ArrLength];
int ResultArr[ArrLength];
x = -1;
tmp = 0;
for (k = 0; k < ArrLength; k++)
{
InArr[k] = 0;
ImArr[k] = 0;
ResultArr[k] = 0;
}
printf("Введите степень 1 многочлена*: ");
scanf("%d", &n);
printf("\nВведите коэффициенты: ");
for (k = 0; k < n; k++)
scanf("%d", &InArr[n - k]);
printf("Введите степень 2 многочлена*: ");
scanf("%d", &m);
printf("\nВведите коэффициенты: ");
for (k = 0; k < m; k++)
scanf("%d", &ImArr[m - k]);
for (i = 0; i <= n*m; i++)
{
for (g = 0; g <= m*n; g++)
{
tmp = InArr * ImArr[g];
if (tmp > 0)
{
x = x + 1;
ResultArr[x] = tmp;
}
}
}
printf("\n");
for (k = ArrLength - 1; k >= 0; k--)
if (ResultArr[k] > 0)
printf("%d ", ResultArr[k]);
}
Умножение 2-х многочленов
Привет. Помогите пожайлуста.
Задача:
По заданным коэффициентам многочлена n-й степени А(х) и многочлена m-й степени B(x) определить коэффициенты многочлена C(x) = A(x) * B(x)
Коэфициенты задает пользователь, например многочлен (3x^2 + 4x + 5), пользователь вводит последовательно 3, 4, 5. Ее нужно сделать на паскале или на С.
Задача:
По заданным коэффициентам многочлена n-й степени А(х) и многочлена m-й степени B(x) определить коэффициенты многочлена C(x) = A(x) * B(x)
Коэфициенты задает пользователь, например многочлен (3x^2 + 4x + 5), пользователь вводит последовательно 3, 4, 5. Ее нужно сделать на паскале или на С.
Реализовать легко, если увидеть кое-какую закономерность. На какую именно сейчас намекну:
Пусть:
A(x) = a0 + a1*x^1 + a2*x^2 + ... + an*x^n
B(x) = b0 + b1*x^1 + b2*x^2 + ... + bm*x^m
Теперь берите поочередно слагаемое из A(x) и умножайте на все слагаемые из B(x). В результате у вас получится новые слагаемые. Сделайте таблицу в таком формате и запишите туда полученные данные:
свободные члены|коэф. для x^1|коэф. для x^2|...|коэф. для x^m|коэф. для x^(m+1)|...|коэф. для x^(m+n)
Далее в каждом столбце смотрите на индексы "а" и "б". В этих индексах вы должны найти ту самую закономерность.
Как только найдете - реализовать код не составит проблем. Заодно запишите код суда.
Пусть:
A(x) = a0 + a1*x^1 + a2*x^2 + ... + an*x^n
B(x) = b0 + b1*x^1 + b2*x^2 + ... + bm*x^m
Теперь берите поочередно слагаемое из A(x) и умножайте на все слагаемые из B(x). В результате у вас получится новые слагаемые. Сделайте таблицу в таком формате и запишите туда полученные данные:
свободные члены|коэф. для x^1|коэф. для x^2|...|коэф. для x^m|коэф. для x^(m+1)|...|коэф. для x^(m+n)
Далее в каждом столбце смотрите на индексы "а" и "б". В этих индексах вы должны найти ту самую закономерность.
Как только найдете - реализовать код не составит проблем. Заодно запишите код суда.
Вы думаете,что следует умножать слагаемые при одинаковых степенях?Ну тогда вы сильно ошибаетесь.Надо перемножать слагаемые при тех степенях,которые в сумме дают одно и то же число
Например,для X в степени 1 и 3,2 и 2 и 3 и 1(в сумме будет 4я степень).Так-то,я это гарантирую!
А вы,прежде чем такое советовать,подумали бы прежде
Например,для X в степени 1 и 3,2 и 2 и 3 и 1(в сумме будет 4я степень).Так-то,я это гарантирую!
А вы,прежде чем такое советовать,подумали бы прежде
Цитата: @pixo $oft
Надо перемножать слагаемые при тех степенях,которые в сумме дают одно и то же число
Я вообще-то это и имел ввиду. Видимо плохо объяснил. Сейчас исправлю.
Поправка: исправил. Спасибо за замечание.
Я реализовывал так:
Записывал в массивы вводимые коэффициенты для А и Б. Перемножал их, но подобные немогу привести из-за того, что незнаю степень. Хотел сделать, так чтобы индекс массива указывал на степень, но не получается...
Вот код:
Записывал в массивы вводимые коэффициенты для А и Б. Перемножал их, но подобные немогу привести из-за того, что незнаю степень. Хотел сделать, так чтобы индекс массива указывал на степень, но не получается...
Вот код:
Код:
Хочу сказать следующее:
1. У вас в циклах присвоения коэффициентам значения выполняется до k-1. т.е. до коэф. для k-1 степени. В условии вместо строго меньше (<) поставьте меньше или равно (<=);
2. Пусть у члена с х степень k. Тогда для него коэф. равен а0*b(k)+a1*b(k-1)+...+a(k-1)b1+ak*b0
3. Ваш код не выведет коэф. если он меньше или равен нулю. А вот пример: (x-1)*(x+1)=(x^2-1)
Очевидно ваша программа выведет "1" и все. А вот 0 (для х^1) и -1 (свободный член) не выведет. Вообще нужно просто создать цикл от нуля до m+n (т.к. у старшего члена будет такая степень).
1. У вас в циклах присвоения коэффициентам значения выполняется до k-1. т.е. до коэф. для k-1 степени. В условии вместо строго меньше (<) поставьте меньше или равно (<=);
2. Пусть у члена с х степень k. Тогда для него коэф. равен а0*b(k)+a1*b(k-1)+...+a(k-1)b1+ak*b0
3. Ваш код не выведет коэф. если он меньше или равен нулю. А вот пример: (x-1)*(x+1)=(x^2-1)
Очевидно ваша программа выведет "1" и все. А вот 0 (для х^1) и -1 (свободный член) не выведет. Вообще нужно просто создать цикл от нуля до m+n (т.к. у старшего члена будет такая степень).
Цитата: Bonez92
Хочу сказать следующее:
Пусть у члена с х степень k. Тогда для него коэф. равен а0*b(k)+a1*b(k-1)+...+a(k-1)b1+ak*b0
Пусть у члена с х степень k. Тогда для него коэф. равен а0*b(k)+a1*b(k-1)+...+a(k-1)b1+ak*b0
По-вашему, общая формула для коэффициента ck (k=0,1,2,...,m+n) многочлена c(x)=a(x)*b(x) имеет следующий вид: ck=bk*a0+bk-1*a1+...+b1*ak-1+b0*ak=SUM(bk-i*ai), i=0,1,2,...,k. Правильно я Вас понял? Если так, то эта формула вкорне неверна и алгоритм на ее основе вычисляет бред сумасшедшего.
P.S. Надеюсь, автор сообщения еще появляется здесь...
Вообще-то формула верна) если [ATTACH=CONFIG]5305[/ATTACH], [ATTACH=CONFIG]5306[/ATTACH], то [ATTACH=CONFIG]5309[/ATTACH], где [ATTACH=CONFIG]5307[/ATTACH]
пруфы можно погуглить))
пруфы можно погуглить))
Цитата: Mr.Hacker
Вообще-то формула верна)
Отлично! Тогда распишите, если Вас не затруднит, коэффициент c5 многочлена c(x)=a(x)*b(x) для случая a(x)=2*x^3+x+1 и b(x)=3*x^2+x+1 по этой формуле.
И, кстати, что такое bn+m в приведенной Вами формуле записи f(x)*g(x), если максимальное значение коэффициента i для bi равно m? Вы где-то содрали еще более неправильную формулу ))
ок..
a(x) :
a0 = 1
a1 = 1
a2 = 0
a3 = 2
a4 = 0
a5 = 0
b(x)
b0 = 1
b1 = 1
b2 = 3
b3 = 0
b4 = 0
b5 = 0
c(x)
c5 = a0*b5+a1*b4+a2*b3+a3*b2+a4*b1+a5*b0 = 0 + 0 + 0 + 2*3 + 0 + 0 = 6
c5 - коэффициент при x^5
вы будете спорить, что он не равен 6?
Это умножение, а не сложение) почувствуйте разницу, максимальная степень результирующего многочлена - сумма степеней многочленов. Доказывать надо или пруф сами поищите?
з.ы. да, согласен)) f(x)g(x) там последняя d должна стоять.. исправил картинку
a(x) :
a0 = 1
a1 = 1
a2 = 0
a3 = 2
a4 = 0
a5 = 0
b(x)
b0 = 1
b1 = 1
b2 = 3
b3 = 0
b4 = 0
b5 = 0
c(x)
c5 = a0*b5+a1*b4+a2*b3+a3*b2+a4*b1+a5*b0 = 0 + 0 + 0 + 2*3 + 0 + 0 = 6
c5 - коэффициент при x^5
вы будете спорить, что он не равен 6?
Это умножение, а не сложение) почувствуйте разницу, максимальная степень результирующего многочлена - сумма степеней многочленов. Доказывать надо или пруф сами поищите?
з.ы. да, согласен)) f(x)g(x) там последняя d должна стоять.. исправил картинку
вообще удивительно, что вы считаете формулу неправильной)) возможно это связано с тем, что здесь принята запись a0 - свободный член, a1 - член при x^1, и т. д., когда обычно в школе и институте для других формул принимают, что a0 - коэффициент при старшем члене и т. д...
вчера тут был текст про то, что многочлены можно представить с Гильбертовом пространстве с базисом (1, x, x^2, x^3, ....) как произведение вектора-столбца коэффициентов на вектор-строку базиса.. Да можно, но это получается нифига не тривиально, ибо умножение в Гильбертовом пространстве - штука сложная.. и считаем мы в итоге не произведение векторов, а их смешанным произведением, то есть вычислением их площади в базисе старшего порядка.. хотя блин старшего порядка тут нет, ибо пространство Гильбертово.. короче муть я тут до этого написал
а товарищу некропостеру, не поленившемуся поднять тему 2009 года и неверное её исправить, предлагаю понять простую вещь..
во-первых, надо понять, что сумма от 0 по 0 будет.. и равна она будет - можно тупо подставить в формулы: k = 0, dk = sum(0, 0)(a(0)b(0-0)) = a0*b0.. свободный член, он собственно от перемножения других свободных и получается
во-вторых, если присмотреться, то в формуле у суммы сверху стоит k, и k такое же стоит у d в индексе.. то бишь при вычислении k-го коэффициента результирующего многочлена мы никогда не уйдём выше k-х коэффициентов исходных..
пример - надо нам вычислить 4ю степень.. раскладывая формулу k = 4, d4 = a0b4 + a1b3 + a2b2 + a3b1 + a4b0..
а по факту.. 4ая степень получается когда? ну допустим в исходных многочленах есть 4ая степень.. тогда получить в результирующем её можно, только умножив эти члены на свободный... ну вот первое и последнее слагаемое это и показывает, a0b4 - свободный член f(x) на коэффициент при 4й степени g(x), a4b0 - свободный член g(x) на коэффициент при 4й f(x).. как ещё можно получить 4ую степень? ну умножить 1ю на 3ю... вот и будет a1b3 и a3b1... a2b2 пояснять надо, не? ))
отсюда мораль: некропост - зло, студенты - зло, не уметь думать - зло))) а всё вместе - зло в кубе)))
вчера тут был текст про то, что многочлены можно представить с Гильбертовом пространстве с базисом (1, x, x^2, x^3, ....) как произведение вектора-столбца коэффициентов на вектор-строку базиса.. Да можно, но это получается нифига не тривиально, ибо умножение в Гильбертовом пространстве - штука сложная.. и считаем мы в итоге не произведение векторов, а их смешанным произведением, то есть вычислением их площади в базисе старшего порядка.. хотя блин старшего порядка тут нет, ибо пространство Гильбертово.. короче муть я тут до этого написал
а товарищу некропостеру, не поленившемуся поднять тему 2009 года и неверное её исправить, предлагаю понять простую вещь..
во-первых, надо понять, что сумма от 0 по 0 будет.. и равна она будет - можно тупо подставить в формулы: k = 0, dk = sum(0, 0)(a(0)b(0-0)) = a0*b0.. свободный член, он собственно от перемножения других свободных и получается
во-вторых, если присмотреться, то в формуле у суммы сверху стоит k, и k такое же стоит у d в индексе.. то бишь при вычислении k-го коэффициента результирующего многочлена мы никогда не уйдём выше k-х коэффициентов исходных..
пример - надо нам вычислить 4ю степень.. раскладывая формулу k = 4, d4 = a0b4 + a1b3 + a2b2 + a3b1 + a4b0..
а по факту.. 4ая степень получается когда? ну допустим в исходных многочленах есть 4ая степень.. тогда получить в результирующем её можно, только умножив эти члены на свободный... ну вот первое и последнее слагаемое это и показывает, a0b4 - свободный член f(x) на коэффициент при 4й степени g(x), a4b0 - свободный член g(x) на коэффициент при 4й f(x).. как ещё можно получить 4ую степень? ну умножить 1ю на 3ю... вот и будет a1b3 и a3b1... a2b2 пояснять надо, не? ))
отсюда мораль: некропост - зло, студенты - зло, не уметь думать - зло))) а всё вместе - зло в кубе)))
Цитата: Mr.Hacker
то бишь при вычислении k-го коэффициента результирующего многочлена мы никогда не уйдём выше k-х коэффициентов исходных..
Вот соль того, что я имел в виду. Нужно дать уточнение о том, что коэффициенты a(x) и b(x) меняются в формуле не от 0 до n и от 0 до m, а от 0 до n+m. При этом значения коэффициентов при степенях от n до n+m и от m до n+m принимаются равными нулю. Выше, когда Вы приводили пример Вы записывали коэффициенты исходных многочленов именно до степени 5, то есть до степени результирующего многочлена. При этом значения коэффициентов ai и bj при i>3 и j>5 принимаются равными нулю. Иначе формулу можно неправильно истолковать, принимая за максимальное значение коэффициентов значения при максимальной степени неопределенной переменной. То есть если подставлять в формулу значения до n и m включительно, то получается муть при значениях k, превышающих степень наименьшего из перемножаемых многочленов.
Например все в том же примере.
Если допустить, что индексы i и j для коэффициентов ai и bj меняется в пределах от 0 до 3 и от 0 до 2 (соответственно), то для k=5 i и j принимают максимально возможное значение, соответствующее степени минимального из двух многочленов (то есть i=2 и j=2), тогда для коэффициента c5 получается следующее:
c5=b2*a0+b1*a1+b0*a2=4.
Таким образом, алгоритм, составленный по приведенной выше формуле вычисления коэффициентов c(x) должен подразумевать приписывание нулей в позиции, соответствующие коэффициентам a(x) и b(x) при степенях больше n и m.
Вообще-то давать такое уточнение не нужно, ибо это основное определение многочлена. http://ru.wikipedia.org/wiki/Многочлен_над_конечным_полем. http://en.wikipedia.org/wiki/Polynomial#Abstract_algebra Мы число 565 можем записать как 0000565, и многочлен аналогично, многочлен x^2+5x-4 можно записать 0*x^4+0*x^3+x^2+5x-4.. А в общем случае 0 старших степеней бесконечно. И это не приписывание нулей старшим коэффициентам, а настоящее определение многочлена.
Неопределённое значение может возникнуть не из неправильного истолкования формул, формулы очевидны и строго опираются на классическую алгебру, а только из того, что при реализации на конкретном языке массивы, которые содержат коэффициенты, ограничены. В бесконечном случае решается обычным ifом, что запрошенное значение превысило значение степени исходного многочлена. У автора в коде, который вы неправильно поняли, если вы внимательно присмотритесь, всё проще. Массивы имеют статический размер 100 и заполняются нулями. Пока многочлен не потребует степень больше 100, его код отработает нормально и вернёт нолики у старших степенй.
А ваше изначальное утверждение было в том, что формула неверна. И оно неверно. А зачем вы такой огромный пост выше написали, я вообще не понимаю)) его можно было свести к одной фразе
Неопределённое значение может возникнуть не из неправильного истолкования формул, формулы очевидны и строго опираются на классическую алгебру, а только из того, что при реализации на конкретном языке массивы, которые содержат коэффициенты, ограничены. В бесконечном случае решается обычным ifом, что запрошенное значение превысило значение степени исходного многочлена. У автора в коде, который вы неправильно поняли, если вы внимательно присмотритесь, всё проще. Массивы имеют статический размер 100 и заполняются нулями. Пока многочлен не потребует степень больше 100, его код отработает нормально и вернёт нолики у старших степенй.
А ваше изначальное утверждение было в том, что формула неверна. И оно неверно. А зачем вы такой огромный пост выше написали, я вообще не понимаю)) его можно было свести к одной фразе