Задача с сайта e-olymp.com.
Засчитанное решение. (C++)
Засчитанное решение. (Java)
Условие задачи
Вводится в символьной форме два многочлена от [latex]x[/latex] с целыми коэффициентами. Вывести их произведение в порядке убывания степеней — также в символьной форме. Степень исходных многочленов не более [latex]10[/latex], коэффициенты исходных многочленов по модулю не более [latex]{ 10 }^{ 4 }[/latex].
Входные данные
В двух строках находятся многочлены.
Выходные данные
В единственной строке выводится многочлен.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 0 0 |
0 |
| 2 | x+1 x-1 |
x^2-1 |
| 3 | -5 x^2+x+x-2x^3 |
10x^3-5x^2-10x |
| 3 | x^10+2x^9+3x^8 -1 |
-x^10-2x^9-3x^8 |
| 4 | x^10+2x^9+3x^8 0 |
0 |
| 5 | x^10+5x^2 x^3-4x |
x^13-4x^11+5x^5-20x^3 |
Решение с использованием класса string
Код программы
|
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#include <iostream> #include <string> #include <vector> using namespace std; int str_to_int(string &s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно). int val = 0; //Возвращает объект типа int, значение которого равно этому числу. bool negative = 0; //Является ли число отрицательным? if(s[begin] == '+') begin++;//Плюс игнорируется. else{ if(s[begin] == '-'){ //Проверка на отрицательность. negative = 1; begin++; } } for(auto i = begin; i < end; ++i){ //Обработка самих цифр числа. val *= 10; val += s[i] - 48; } if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица if(negative == 1) val *= -1; return val; } string int_to_str(int val){ //Возвращает строку с записанным в ней числом val. string s, tmp; if(val > 0) s.push_back('+'); //Проверка на отрицательность. else{ val *= -1; s.push_back('-'); } while(val > 0){ tmp.push_back(val%10 + 48); //В tmp хранится запись числа в обратном порядке. val /= 10; } for(int i = tmp.size()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке. s.push_back(tmp[i]); } return s; } void erase_the_plus(string &s){ //Удаляет плюс, стоящий в начале строки. if(s[0] == '+') s.erase(s.begin()); } void erase_the_one(string &s){ //Удаляет единицу из строк вида "+1", "-1". if((s[1] == '1') && (s.size() == 2)) s.erase(s.begin()+1); } void analyze(string &s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х. if(s.find("x") == string::npos) v[0] += str_to_int(s, 0, s.size()); //Если в строке содержится запись константаы. else{ if(s.find("^") == string::npos) v[1] += str_to_int(s, 0, s.find("x")); //Строка вида "ax". else{ int power = str_to_int(s, s.find("^") + 1, s.size()); //Строка вида "ax^y". v[power] += str_to_int(s, 0, s.find("x")); } } } vector <int> decompose(string &s){ //Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них. vector <int> v(11); string cur_s; int i = 0; while(i < s.size()){ cur_s.clear(); cur_s.push_back(s[i]); i++; while((s[i] != '+') && (s[i] != '-') && (i < s.size())){ //cur_s - анализируемое в данный момент слагаемое. cur_s.push_back(s[i]); i++; } analyze(cur_s, v); } return v; } vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов. vector <int> c(21); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них. for(int i = 0; i < c.size(); ++i) c[i] = 0; for(int i = 0; i < a.size(); ++i){ for(int j = 0; j < b.size(); ++j){ c[i + j] += a[i] * b[j]; } } return c; } string compose(vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен. string s; for(int i = v.size() - 1; i >= 2; --i){ if(v[i] != 0){ string coef = int_to_str(v[i]); //Коэффициент. erase_the_one(coef); s = s + coef; s.push_back('x'); s.push_back('^'); string power = int_to_str(i); //Степень х. erase_the_plus(power); s = s + power; } } if(v[1] != 0){ //Записи слагаемых с первой и нулевой степенями х отличаются. string coef = int_to_str(v[1]); erase_the_one(coef); s = s + coef; s.push_back('x'); } if(v[0] != 0){ s = s + int_to_str(v[0]); } return s; } int main() { string a,b; vector <int> a_decomposed(11, 0); vector <int> b_decomposed(11, 0); getline(cin, a); //Ввод многочленов. getline(cin, b); a_decomposed = decompose(a); b_decomposed = decompose(b); vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed); string c = compose(c_decomposed); erase_the_plus(c); //Удаляется первый плюс, если он есть. if(c.size() > 0) cout << c; else cout << 0; //Если в ответе получаем константу 0. return 0; } |
Нажмите, чтобы выполнить его на ideone.com.
Описание
Сначала в функции main объявляются две строки a и b. В них водятся исходные два многочлена. Но в форме строк, особенно учитывая, что подобные слагаемые не всегда приведены, умножать многочлены не удобно. Потому объявляются три вектора: a_decomposed, b_decomposed и c_decomposed. Первые два имеют размер [latex]11[/latex], поскольку в условии сказано, что многочлены могут быть от нулевой до десятой степени включительно. В них элемент с индексом [latex]i[/latex] равняется коэффициенту при слагаемом многочлена, в котором [latex]x[/latex] имеет степень [latex]i[/latex]. Они заполняются при помощи функции decompose. В ней при помощи функции analyze отдельно анализируется каждое слагаемое многочлена, и результат заносится в вектор. c_decomposed хранит коэффициенты многочлена, полученного умножением двух исходных. Значения его элементов вычисляются при помощи функции multiplicate. После в ходе работы функции compose многочлен в требуемой форме записывается в строку c. Далее, если её первым символом является [latex]+[/latex], он удаляется из строки. Наконец, если c — непустая строка, она выводится. Иначе выводится [latex]0[/latex].
Решение с использованием c-string
Код программы
|
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
#include <iostream> #include <cstring> #include <vector> using namespace std; int str_to_int(char *s, int begin, int end){//Принимает адрес первого элемента строки и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно). int val = 0; //Возвращает объект типа int, значение которого равно этому числу. bool negative = 0; //Является ли число отрицательным? if(s[begin] == '+') begin++;//Плюс игнорируется. else{ if(s[begin] == '-'){ //Проверка на отрицательность. negative = 1; begin++; } } for(auto i = begin; i < end; ++i){ //Обработка самих цифр числа. val *= 10; val += s[i] - 48; } if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица if(negative == 1) val *= -1; return val; } void int_to_str(int val, char *s){ //Записывает в строку s число val. char tmp[5]; if(val > 0) s[0] = '+'; //Проверка на отрицательность. else{ val *= -1; s[0] = '-'; } int i = 0; while(val > 0){ tmp[i] = (val%10 + 48); //В tmp хранится запись числа в обратном порядке. val /= 10; i++; } tmp[i] = 0; int j = 1; for(i = strlen(tmp)-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке. s[j] = tmp[i]; j++; } s[j] = 0; //Если строка получилась короче пяти символов, нужно поставить после последнего нулевой символ. } void erase_the_plus(char *s){ //Удаляет плюс, стоящий в начале строки. if(s[0] == '+'){ for(int i = 0; s[i] != 0; ++i){ s[i] = s[i+1]; } } } void erase_the_one(char *s){ //Удаляет единицу из строк вида "+1", "-1". if((s[1] == '1') && (strlen(s) == 2)){ s[1] = 0; } } void analyze(char *s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х. if(strchr(s, 'x') == NULL) v[0] += str_to_int(s, 0, strlen(s)); //Если в строке содержится запись константаы. else{ if(strchr(s, '^') == NULL) v[1] += str_to_int(s, 0, strchr(s, 'x') - s);//Строка вида "ax". else{ int power = str_to_int(s, strchr(s, '^') - s + 1, strlen(s)); v[power] += str_to_int(s, 0, strchr(s, 'x') - s); } } } vector <int> decompose(char *s){//Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них. vector <int> v(11); char cur_s[10]; int i = 0, j; while(s[i] != 0){ //cur_s[0] = 0; cur_s[0] = s[i]; i++; j = 1; while((s[i] != '+') && (s[i] != '-') && (s[i] != 0)){ //cur_s - анализируемое в данный момент слагаемое. cur_s[j] = s[i]; i++; j++; } cur_s[j] = 0; analyze(cur_s, v); } return v; } vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов. vector <int> c(21); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них. for(int i = 0; i < c.size(); ++i) c[i] = 0; for(int i = 0; i < a.size(); ++i){ for(int j = 0; j < b.size(); ++j){ c[i + j] += a[i] * b[j]; } } return c; } void compose(char *s, vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен. for(int i = v.size() - 1; i >= 2; --i){ if(v[i] != 0){ char coef[6]; //Коэффициент. int_to_str(v[i], coef); erase_the_one(coef); strcat(s, coef); strcat(s, "x"); strcat(s, "^"); char power[2]; //Степень х. int_to_str(i, power); erase_the_plus(power); strcat(s, power); } } if(v[1] != 0){ //Записи слагаемых с первой и нулевой степенями х отличаются. char coef[6]; int_to_str(v[1], coef); erase_the_one(coef); strcat(s, coef); strcat(s, "x"); } if(v[0] != 0){ char coef[6]; int_to_str(v[0], coef); strcat(s, coef); } } int main() { char *a, *b; int max_number_of_symbols = 100; a = new char[max_number_of_symbols]; b = new char[max_number_of_symbols]; vector <int> a_decomposed(11, 0); vector <int> b_decomposed(11, 0); cin.getline(a, max_number_of_symbols); //Ввод многочленов. cin.getline(b, max_number_of_symbols); a_decomposed = decompose(a); b_decomposed = decompose(b); vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed); char *c; c = new char[max_number_of_symbols]; compose(c, c_decomposed); erase_the_plus(c); //Удаляется первый плюс, если он есть. if(strlen(c) > 0) cout << c; else cout << 0; //Если в ответе получаем константу 0. return 0; } |
Нажмите, чтобы выполнить его на ideone.com.
Описание
Алгоритм решения тот же. Следует отметить: поскольку объекты типа char* «не знают» свою длину, и в силу других причин, в некоторых местах программы используются «магические числа». Однако они не взяты случайно, а продиктованы условием задачи (к примеру, тем, что максимальная степень исходных многочленов — [latex]10[/latex] и т.п.). Только подходящее значение переменной max_number_of_symbols было найдено эмпирически.
Решение на Java
Код программы
|
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
import java.util.*; class Main { static int strToInt(String s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно). int val = 0; //Возвращает объект типа int, значение которого равно этому числу. boolean negative = false; //Является ли число отрицательным? if(s.charAt(begin) == '+') begin++;//Плюс игнорируется. else{ if(s.charAt(begin) == '-'){ //Проверка на отрицательность. negative = true; begin++; } } for(int i = begin; i < end; ++i){ //Обработка самих цифр числа. val *= 10; val += s.charAt(i) - 48; } if(val == 0 && s.charAt(begin) != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица if(negative == true) val *= -1; return val; } static String intToStr(int val){ //Возвращает строку с записанным в ней числом val. String s = "", tmp = ""; if(val > 0) s = s + "+"; //Проверка на отрицательность. else{ val *= -1; s = s + "-"; } while(val > 0){ tmp = tmp + Integer.toString(val%10); //В tmp хранится запись числа в обратном порядке. val /= 10; } for(int i = tmp.length()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке. s = s + tmp.charAt(i); } return s; } static String eraseThePlus(String s){ //Удаляет плюс, стоящий в начале строки. if(s.charAt(0) == '+') s = s.substring(1, s.length()); return s; } static String eraseTheOne(String s){ //Удаляет единицу из строк вида "+1x", "-1x^y". if((s.charAt(1) == '1') && (s.length() == 2)) s = s.charAt(0) + s.substring(2, s.length()); return s; } static void analyze(String s, Vector v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х. for(int i = 0; i < 11; ++i) v.addElement(0); if(s.indexOf('x') == -1) v.set(0, (int)(v.elementAt(0)) + strToInt(s, 0, s.length())); else{ if(s.indexOf('^') == -1) v.set(1, (int)(v.elementAt(1)) + strToInt(s, 0, s.indexOf("x"))); //Строка вида "ax". else{ int power = strToInt(s, s.indexOf("^") + 1, s.length()); //Строка вида "ax^y". v.set(power, (int)(v.elementAt(power)) + strToInt(s, 0, s.indexOf("x"))); } } } static Vector decompose(String s){ //Разбивает многочлен на слогаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них. Vector v = new Vector(); String cur_s = ""; int i = 0; while(i < s.length()){ cur_s = ""; cur_s = cur_s + s.charAt(i); i++; while((i < s.length()) && (s.charAt(i) != '+') && (s.charAt(i) != '-')){ //cur_s - анализируемое в данный момент слогаемое. cur_s = cur_s + s.charAt(i); i++; } analyze(cur_s, v); } return v; } static Vector multiplicate (Vector a, Vector b){ //Умножение многочленов. Vector c = new Vector(); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них. for(int i = 0; i < 21; ++i) c.addElement(0); for(int i = 0; i < 11; ++i){ for(int j = 0; j < 11; ++j){ c.set(i+j, ((int)(c.elementAt(i+j)))+((int)(a.elementAt(i)))*((int)(b.elementAt(j)))); } } return c; } static String compose(Vector v){ //Из элементов вектора составляет строку, в которой записан многочлен. String s = ""; for(int i = v.size() - 1; i >= 2; --i){ if((int)v.elementAt(i) != 0){ String coef = intToStr((int)v.elementAt(i)); //Коэффициент. coef = eraseTheOne(coef); s = s + coef; s = s + "x"; s = s + "^"; String power = intToStr(i); //Степень х. power = eraseThePlus(power); s = s + power; } } if((int)v.elementAt(1) != 0){ //Записи слогаемых с первой и нулевой степенями х отличаются. String coef = intToStr((int)v.elementAt(1)); coef = eraseTheOne(coef); s = s + coef; s = s + "x"; } if((int)v.elementAt(0) != 0){ s = s + intToStr((int)v.elementAt(0)); } return s; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); String a = in.nextLine(); String b = in.nextLine(); String c = new String(); Vector a_decomposed = new Vector(11); Vector b_decomposed = new Vector(11); a_decomposed = decompose(a); b_decomposed = decompose(b); Vector c_decomposed = multiplicate(a_decomposed, b_decomposed); c = compose(c_decomposed); if(c.length() > 0){ c = eraseThePlus(c); //Удаляется первый плюс, если он есть. System.out.print(c); } else System.out.print(0); //Если в ответе получаем константу 0. } } |
Нажмите, чтобы выполнить его на ideone.com.
Хорошо.
— Немного поправил орфографию (сложение, но слагаемое).
— Если будет время посмотрите как используют быстрое преобразование Фурье для ускорения умножения многочленов и длинных чисел. Интересная и полезная тема. Часто бывает полезной. Удивительно, что до этого додумались (Штрасен) всего 50 лет назад.