e-olymp 1243. Наименьшее общее кратное

20/12/2020 by Максим Ливитчук

Условие

Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.

Вам необходимо найти $НОК$ $m$ заданных чисел.

Входные данные

Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.

Выходные данные

Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.

Тесты

№	ввод	вывод
1	2 3 5 7 15 6 4 10296 936 1287 792 1	105 10296
2	3 1 36 5 2 2 2 2 2 5 987 1597 2584 4181 6765 10946 17711	36 2 38400890173772280
3	0

Код

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/__gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

cin >>n;

for(int i=0; i<n; i++) {

cin >>m;

int temp, ans;

cin >>ans;

for(int j=1; j<m; j++) {

cin >>temp;

ans = ans/__gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Код с алгоритмом Евклида

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
  while(a and b) {
    if(a>b)
      a %= b;
    else
      b %= a;
  }
  return a+b;
}

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int gcd(int a, int b) {

while(a and b) {

if(a>b)

a %= b;

else

b %= a;

}

return a+b;

}

int main() {

int n, m;

cin >>n;

for(int i=0; i<n; i++) {

cin >>m;

int temp, ans;

cin >>ans;

for(int j=1; j<m; j++) {

cin >>temp;

ans = ans/gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Решение

$\DeclareMathOperator{\lcm}{lcm}$
$НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.

$НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.

Ссылки

Related Images:

e-olymp 1679. Честная цепочка

19/12/2020 by Максим Ливитчук

Условие

В подземных норах в долине рядом со скалами Крейд-Моор долгое время жили в мире и согласии два гномьих племени. Гномы обоих племен работали в шахтах, добывая драгоценные камни. Первое племя добывало исключительно изумруды, а второе племя — рубины. Однажды в честь великого праздника Файрвинд гномы решили принести в дар своей богине Мирабель цепочку из изумрудов и рубинов. Самые искусные кузнецы обоих племен работали над созданием этой цепочки, собирая на ней один за одним драгоценные камни. Но как только работа была окончена, решили вожди племен пересчитать камни каждого вида. Ведь если каких-то камней окажется меньше, то богиня может отвернуться от племени, которое пожадничало. Чтобы избежать подобных последствий, было решено подарить некоторый непустой фрагмент цепочки (то есть цепь, состоящую из нескольких камней, расположенных друг за другом в исходной цепочке), в котором будет рубинов ровно столько же, сколько и изумрудов. Возможно это может быть сделано несколькими способами. Для того, чтобы узнать сколько таких способов существует, гномы обратились за помощью к вам.

Напишите программу, которая находит количество способов, которыми можно выбрать подходящий фрагмент.

Входные данные

В единственной строке задается последовательность камней в исходной цепочке: символ E обозначает изумруд, символ R — рубин. Количество символов в строке не превышает $500000$.

Выходные данные

Выведите количество способов, которыми можно выбрать фрагмент с одинаковым количеством изумрудов и рубинов.

Тесты

№	ввод	вывод
1	REER	3
2	REERREER	12
3	RRRRRRRR	0
4	EREREERERERREREREEERERERERERRREREREERERERERE	273
5	REEERREE	7

Код

#include <iostream>
#include <map>
using namespace std;

int main() {
    int cnt = 0;
    char buf;
    map<int, long long> mp;
    mp[0] = 1;
    while(cin >>buf) {
        if(buf=='R')
            cnt++;
        else
            cnt--;
        mp[cnt]++;
    }
    long long answer = 0;
    for(auto e: mp) {
        answer += e.second*(e.second-1)/2;
    }
    cout <<answer;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map<int, long long> mp;

mp[0] = 1;

while(cin >>buf) {

if(buf=='R')

cnt++;

else

cnt--;

mp[cnt]++;

}

long long answer = 0;

for(auto e: mp) {

answer += e.second*(e.second-1)/2;

}

cout <<answer;

}

Компактный код

#include 
#include <map>
using namespace std;
 
int main() {
    int cnt = 0;
    char buf;
    map mp;
    mp[0] = 1;
    while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;
    long long a = 0;
    for(auto e: mp) a += e.second*(e.second-1)/2;
    cout <<a;
}

#include

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map mp;

mp[0] = 1;

while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;

long long a = 0;

for(auto e: mp) a += e.second*(e.second-1)/2;

cout <<a;

}

Решение

Составим массив из $n+1$ чисел, каждое из которых будет располагаться в месте возможного начала или конца фрагмента цепочки, который гномы должны вручить богине. Число в самом начале цепочки возьмём равным $0$, а все следующие числа будут представлять из себя количество R минус количество E, встречающихся в фрагменте с начала до этого числа.

Наглядный пример такого массива для пятого примера (подписан как cnt)

На таком массиве наглядно видно, что правильным фрагментом будет любой, начинающийся и кончающийся одинаковым числом, ведь это значит что между этими числами равное количество как R($+1$), так и E($-1$), которые сокращаются.

Выделенные в том же примере фрагменты с началом и концом в 0 и -2

Так как нам не важны конкретные правильные фрагменты, а только их суммарное количество, нам будет достаточно знать, сколько раз в массиве встречается то или иное число. В коде эту информацию хранит ассоциативная таблица mp. Запись mp[cnt]++; создаёт новый равный нулю элемент по ключу cnt, если раньше в структуре его не было, после чего инкрементирует значение.
Сам же массив воспроизводится на ходу из ввода, в переменной cnt. В конце программы количество фрагментов считается как сумма $\frac{n(n-1)}{2}$, где $n$ — mp[i] для всех встречавшихся в массиве чисел.

Ссылки

Related Images:

e-olymp 8678. Birches

05/06/2019 by Виктор Иванов

Task

The State National Park $Q$ recently acquired a beautiful birch avenue consisting of $n$ trees. Each tree has a height of $H_i$.

International Classification of national parks is a list of the most beautiful nature reserves in the world. Used to rank parks such a thing as $distinctiveness$ which is understood as the number of pairs ($i$, $j$), for which the observed ratio of $H_i$ $mod$ $H_j$ = $k$, where $k$ is a special number, which is selected by the Expert Council of the international organization of national parks.

What $distinctiveness$ has national park state $Q$?

Input

The first line has two positive integers $n$ and $k$ [latex]\left(1\leqslant n\leqslant 10^5, 0\leqslant k\leqslant 10^6\right)[/latex] — the number of trees in the national park and a special number of the advisory council, respectively.

The second line has $n$ numbers $H_i$ [latex]\left(1\leqslant H_i\leqslant 10^6\right)[/latex] — the height of the trees in the park.

Output

In the single line print $Q$ national park $distinctiveness$.

Tests

№	Input	Output
1	5 1 1 2 3 4 5	8
2	6 2 2 6 7 8 10 14	8
3	15 6 1 4 5 6 9 13 15 16 19 20 2124 27 45 49	14
4	7 3 1 5 7 8 9 23 46	2
5	10 15 23 26 67 79 82 110 118 200 450 900	2

Program code

#include <iostream>
#define SIZE 1000001
using namespace std;

long long n, k, a, cnt[SIZE], i, j, x = 0;
int main() {
    cin >> n >> k;
    for (i = 0; i < n; ++i) {
        cin >> a;
        ++cnt[a];
    }
    for (i = k + 1; i < SIZE; ++i) {
        if (cnt[i] > 0) {
            for (j = k; j < SIZE; j += i) //add each time k + 1
                if (cnt[j] > 0) {
                    if (i == j) {
                        x += cnt[i] * (cnt[i] - 1);
                    }
                    else {
                        x += cnt[j] * cnt[i];
                    }
            }
        }
    }
    cout << x << endl;
}

#include <iostream>

#define SIZE 1000001

using namespace std;

long long n, k, a, cnt[SIZE], i, j, x = 0;

int main() {

cin >> n >> k;

for (i = 0; i < n; ++i) {

cin >> a;

++cnt[a];

}

for (i = k + 1; i < SIZE; ++i) {

if (cnt[i] > 0) {

for (j = k; j < SIZE; j += i) //add each time k + 1

if (cnt[j] > 0) {

if (i == j) {

x += cnt[i] * (cnt[i] - 1);

}

else {

x += cnt[j] * cnt[i];

}

cout << x << endl;

}

Solution

To solve this problem, we will count the number of identical elements, while entering the array. Next, if $i$ and $j$ were met more than $0$ times and $i$ is not equal $j$, we add the counter x + = cnt [j] * cnt [i], and if $i$ = $j$ — x + = cnt [i] * (cnt [i] - 1).

e-olymp 6264. Энергетический магнат

01/02/2019 by Виктор Иванов

Задача

Маленький Вася играет в новую компьютерную игру — пошаговую стратегию «Энергетический магнат».

Правила игры достаточно просты:

- Доска содержит [latex]n[/latex] слотов, расположенных в линию.
- Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
- Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
- После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.

Пример №1.

Вася уже знает все типы электростанций, которые он сможет построить на каждом шаге игры. Он хочет знать, какое максимальное количество очков он сможет получить в игре. Можете ли Вы ему помочь?

Входные данные

Первая строка содержит число [latex]n \left(1\leqslant n\leqslant 1000 \right)[/latex] — количество слотов на доске. Вторая строка содержит строку [latex]s[/latex]. [latex]i[/latex]-ый символ строки равен [latex]1[/latex], если Вы можете построить однослотовую электростанцию в [latex]i[/latex]-ом раунде, и символ [latex]2[/latex], если Вы можете построить двуслотовую электростанцию в [latex]i[/latex]-ом раунде. Количество раундов в игре не превосходит [latex]100000[/latex].

Выходные данные

Вывести одно число — наибольшее количество очков, которое можно достичь.

Тесты

№	Вхлодные данные	Выходные данные
1	3 21121	10
2	2 12	2
3	2 211	4

Код программы

#include <iostream>
using namespace std;

int main() {
    long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.
    long temp;  //temp - количество свободных слотов.
    cin >> n;
    temp = n;
    char s;
    while(cin >> s) {
        c = (s - '0');
        num += (c == 2) ? 1 : 0;
        if (temp - c < 0 && num >= 1) {
            temp += (2 - c);
            num -= 1;
        }
        else if (temp - c >= 0) {
            temp -= c;
        }
        res += (num < 1) ? (n - temp) : (n - temp - num);
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.

long temp; //temp - количество свободных слотов.

cin >> n;

temp = n;

char s;

while(cin >> s) {

c = (s - '0');

num += (c == 2) ? 1 : 0;

if (temp - c < 0 && num >= 1) {

temp += (2 - c);

num -= 1;

}

else if (temp - c >= 0) {

temp -= c;

}

res += (num < 1) ? (n - temp) : (n - temp - num);

}

cout << res;

return 0;

}

Решение задачи

Будем увеличивать num на 1, если встречается двуслотовая электростанция. Если нет свободных слотов [latex]temp — c\lt0[/latex] и [latex]num\geqslant1[/latex], то вместо двуслотовой ставим станцию, которая в этом ходе должна быть [latex]temp += (2 — c)[/latex] и вычитаем одно очко. В итоге смотрим, если двуслотовых электростанций нет [latex]num\gt 1[/latex], то считаем однослотовые: [latex]n — temp[/latex], а если они есть, то: [latex]n — temp — num[/latex].

Ссылки

Условие задачи на e-olymp
Код программы ideone

Related Images:

e-olymp 446. Ровные делители

18/09/2018 by Александр Дьяченко

Задача

Натуральное число $m$ называется ровным делителем числа $n$, если частное и остаток от деления $n$ на $m$ равны. По заданному натуральному числу $n$ найти количество его ровных делителей.

Входные данные

Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.

Выходные данные

Выведите искомое количество ровных делителей числа $n$.

Тесты

Входные данные	Выходные данные
5	1
20	2
200	6
653	1
5982	4

Код программы

#include <iostream>
using namespace std;

int main() {
    unsigned n, q = 0;
    cin >> n;
    for (int m = 1; m <= n; m++)
        if (n / m == n % m)
            q += 1;
    cout << q;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned n, q = 0;

cin >> n;

for (int m = 1; m <= n; m++)

if (n / m == n % m)

q += 1;

cout << q;

return 0;

}

Решение

Для решения этой задачи сперва введем переменную q, в которой будем хранить количество ровных делителей числа $n$. Затем запустим цикл, который будет проверять каждое из чисел от $1$ до $n$ включительно, является ли оно ровным делителем. Если условие выполняется, то увеличиваем значение, хранящееся в q на единицу. После цикла выведем искомое на экран.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Related Images:

e-olymp 58. Биллиард

05/08/2018 by Александр Дьяченко

Задача

Биллиард представляет собой прямоугольник размерами $M \times N$, где $M$ и $N$ — натуральные числа. Из верхней левой лузы вылетает шар под углом $45^{\circ}$ к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

Входные данные

Во входной строке два числа $M$ и $N$, $1 ≤ M, N ≤ 2000000000$. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. $M$ — горизонтальная сторона биллиарда, $N$ — вертикальная сторона биллиарда.

Выходные данные

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные	Выходные данные
2 1	1 2
5 6	9 4
12 33	13 2
156 156	0 3
654 236	443 4

Код программы

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long m, n;
    cin >> m >> n;
    long g = __gcd(m, n);
    m /= g;
    n /= g;
    cout << (n + m - 2) << " ";
    if(n % 2 == 0 and m % 2 != 0) cout << 4;
    if(n % 2 != 0 and m % 2 != 0) cout << 3;
    if(n % 2 != 0 and m % 2 == 0) cout << 2;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long m, n;

cin >> m >> n;

long g = __gcd(m, n);

m /= g;

n /= g;

cout << (n + m - 2) << " ";

if(n % 2 == 0 and m % 2 != 0) cout << 4;

if(n % 2 != 0 and m % 2 != 0) cout << 3;

if(n % 2 != 0 and m % 2 == 0) cout << 2;

return 0;

}

Решение

Чтобы решить эту задачу, необходимо найти НОД значений $M$ и $N$ из условия. Для этого, сперва нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали во $2$ строке. Далее, в $8$ строке, введем перемененную g и присвоим ей значение НОД для $M$ и $N$. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Related Images:

e-olymp 1482. Умножение матриц

25/06/2018 by Томас Пасенченко

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

Входные данные

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

Выходные данные

В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.

Тесты

Входные данные	Выходные данные
2 3 1 3 4 5 -2 3 3 3 1 3 2 2 1 3 0 -1 1	2 3 7 2 15 1 10 7
3 3 1 5 3 2 6 1 7 -1 -3 3 2 3 6 -1 1 3 1	3 2 7 14 3 19 13 38
4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2 4 4 1 0 0 0 0 1 0 0 0 0 1 0	4 4 4 8 -18 16 3 7 14 -42 2 1 1 7 4 9 5 -2
3 3 5 7 -1 8 9 3 0 -6 17 2 3 7 -15 1 8 8 2	-1
2 3 57 -49 31 89 11 -37 3 1 19 -19 0	2 1 2014 1482

Код программы

#include <iostream>
using namespace std;

int main() {
    int na, ma, nb, mb;
    cin >> na >> ma;
    int **a = new int *[na];
    for (int i = 0; i < na; i++) {
        a[i] = new int[ma];
    }
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < ma; j++) {
            cin >> a[i][j];
        }
    }
    cin >> nb >> mb;
    // Проверяем возможность вычисления произведения матриц
    if (ma != nb) {
        cout << -1;
        return 0;
    }
    int **b = new int *[nb];
    for (int i = 0; i < nb; i++) {
        b[i] = new int[mb];
    }
    for (int i = 0; i < nb; i++) {
        for (int j = 0; j < mb; j++) {
            cin >> b[i][j];
        }
    }
    
    int **c = new int *[na];
    for (int i = 0; i < na; i++) {
        c[i] = new int[mb];
    }
    // Вычисляем произведение
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < mb; j++) {
            for (int r = 0; r < ma; r++) {
                c[i][j] += a[i][r] * b[r][j];
            }
        }
    }
    // Выводим результат
    cout << na << " " << mb << "\n";
    for (int i = 0; i < na; i++) {
        for (int j = 0; j < mb; j++) {
            cout << c[i][j];
            if (j + 1 != mb) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int na, ma, nb, mb;

cin >> na >> ma;

int **a = new int *[na];

for (int i = 0; i < na; i++) {

a[i] = new int[ma];

}

for (int i = 0; i < na; i++) {

for (int j = 0; j < ma; j++) {

cin >> a[i][j];

}

cin >> nb >> mb;

// Проверяем возможность вычисления произведения матриц

if (ma != nb) {

cout << -1;

return 0;

}

int **b = new int *[nb];

for (int i = 0; i < nb; i++) {

b[i] = new int[mb];

}

for (int i = 0; i < nb; i++) {

for (int j = 0; j < mb; j++) {

cin >> b[i][j];

}

int **c = new int *[na];

for (int i = 0; i < na; i++) {

c[i] = new int[mb];

}

// Вычисляем произведение

for (int i = 0; i < na; i++) {

for (int j = 0; j < mb; j++) {

for (int r = 0; r < ma; r++) {

c[i][j] += a[i][r] * b[r][j];

}

// Выводим результат

cout << na << " " << mb << "\n";

for (int i = 0; i < na; i++) {

for (int j = 0; j < mb; j++) {

cout << c[i][j];

if (j + 1 != mb) cout << " ";

}

cout << "\n";

}

return 0;

}

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$

Ссылки

Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia

Related Images:

e-olymp 2860. Сумма чисел на промежутке

05/12/2017 by Александр Дьяченко

Задача

Найти сумму целых чисел на промежутке от $a$ до $b$.

Входные данные

Два целых числа $a$ и $b$, по модулю не превышающих $10^9$.

Выходные данные

Сумма целых чисел на промежутке от $a$ до $b$.

Тесты

Входные данные	Выходные данные
2 5	14
249 318	19845
23 69	2162
124 200	12474
478 653	99528

Код программы

#include <iostream>
using namespace std;

int main() {
    long a, b, n, S;
    cin >> a >> b;
    n = b - a + 1;
    S = (a + b) * n / 2;
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long a, b, n, S;

cin >> a >> b;

n = b - a + 1;

S = (a + b) * n / 2;

cout << S;

return 0;

}

Решение

Для того, что бы найти ответ, нам необходимо знание формул прогрессии, так как решением данной задачи является сумма $n$ первых членов арифметической прогрессии. Вычислить её можно по формуле $\displaystyle S_n = \frac{a_1 + a_n}{2} \cdot n$, где $a_1$ — это a из входного потока, а $a_n$ — это b. Тем не менее, мы все ещё не можем применить вышеприведенную формулу, так как нам неизвестно $n$. Выведем же его из формулы $n$-ого члена арифметической прогрессии: $a_n = a_1 + d \cdot (n-1)$, где $d$ — это разность арифметической прогрессии, которая по условию (хоть и негласно) равна единице. Зная это, из последней формулы выведем, что $n = a_n-a_1 + 1$. Теперь же, когда мы знаем все необходимые значения, остается только подсчитать сумму арифметической прогрессии по ранее данной формуле и подать результат на выход.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Related Images:

e-olymp 112. Торт

26/11/2017 by Илья Черноморец

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

Сколько времени потребуется толстякам, чтобы съесть весь праздничный торт вместе?

Входные данные

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $10000$.

Выходные данные

Вывести время в часах, за которое толстяки вместе могут съесть торт. Результат округлить до двух десятичных знаков.

TESTS

$t_1$	$t_2$	$t_3$	$t$
3	3	3	1.00
4	67	50	3.51
228.22	8	2.28	1.76
1577	157.7	15.77	14.21

C ветвлением:

#include<iostream>
#include<iomanip>

using namespace std;
int main(){
    double t1,t2,t3;
    cin >> t1 >> t2 >> t3;
    double t;
    t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);
    if(t1*t2*t3 == 0) cout<<0;
        else cout<<fixed<<setprecision(2)<<t;
    return 0;
}

#include<iostream>

#include<iomanip>

using namespace std;

int main(){

double t1,t2,t3;

cin >> t1 >> t2 >> t3;

double t;

t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);

if(t1*t2*t3 == 0) cout<<0;

else cout<<fixed<<setprecision(2)<<t;

return 0;

}

Без ветвления:

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    double t1, t2, t3;
    cin >> t1 >> t2 >> t3;
    double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;
    cout << setprecision(2) << fixed << t;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

double t1, t2, t3;

cin >> t1 >> t2 >> t3;

double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;

cout << setprecision(2) << fixed << t;

return 0;

}

Решение с ветвлением

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t_1}-\frac{t}{t_2}-\frac{t}{t_3}=0;$
$\frac{t}{t_1}+\frac{t}{t_2}+\frac{t}{t_3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t\left(t_1t_2+t_2t_3+t_1t_3\right)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Решение без ветвления

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $\left(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}\right)$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков. Для этого воспользуемся функцией setprecision() и её аргументом fixed

cout << setprecision(2) << fixed << t;

1	cout << setprecision(2) << fixed << t;

Ссылки

Условие задачи e-olymp
Код решения

Related Images:

A 325. Простые делители числа

28/08/2017 by Курьянов Павел

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные	выходные данные
2	2
7	7
50	2 5 5
169	13 13
583	11 53
2368	2 2 2 2 2 2 37
73890	2 3 3 5 821
885066	2 3 7 13 1621
6943960340	2 2 5 97 1787 2003

Код программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    unsigned long long n;
  cin>>n;
    
    for (unsigned long long i = 2; i < sqrt(n)+0.00001; )    {
        if ( n % i == 0 ){
            std::cout << i << ' ';
            n /= i;
        }
        else{
            ++i;
        }
    }
    if ( n > 1 )
        std::cout << n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

unsigned long long n;

cin>>n;

for (unsigned long long i = 2; i < sqrt(n)+0.00001; ) {

if ( n % i == 0 ){

std::cout << i << ' ';

n /= i;

}

else{

++i;

}

if ( n > 1 )

std::cout << n;

return 0;

}

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

Условие задачи(страница 135)
Код на ideone

Related Images:

KM208(a). Наибольшая разность чисел последовательности

05/10/2016 by Вадим Гордийчук

Задача

Известно, что разность между наибольшим и наименьшим из вещественных чисел [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_{10}[/latex] равна [latex]1[/latex]. Какой наибольшей может быть разность между наибольшим и наименьшим из [latex]10[/latex] чисел [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_{10}}{10}[/latex]?

Каков будет ответ, если чисел не [latex]10[/latex], а [latex]n[/latex]?

Входные данные

Количество элементов последовательности [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_n[/latex].

Выходные данные

Наибольшая разность наибольшего и наименьшего элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n} {n}[/latex].

Тесты

Входные данные	Выходные данные
2	0.5
4	0.75
6	0.833333
8	0.875

Код программы

#include <iostream>
using namespace std;

int main()
{
    int amount_of_elements; double biggest_difference;
    cin >> amount_of_elements;
    biggest_difference = 1 - 1.0/amount_of_elements;
    cout << biggest_difference;
}

#include <iostream>

using namespace std;

int main()

{

int amount_of_elements; double biggest_difference;

cin >> amount_of_elements;

biggest_difference = 1 - 1.0/amount_of_elements;

cout << biggest_difference;

}

Решение задачи

Выведем формулу сразу для [latex]n[/latex] чисел. Сделаем несколько предварительных замечаний.

Обозначим через [latex]y_k[/latex] число [latex]\frac{x_1+x_2+ \ldots+x_k}{k}[/latex], где [latex]k=1, 2, 3, \ldots, n[/latex]. Если прибавить ко всем [latex]x_i[/latex] некоторое число [latex]a[/latex], то вместо чисел [latex]y_i[/latex] мы получим числа [latex]y_i+a[/latex]. Максимальные разности для чисел [latex]y_i[/latex] и для [latex]y_i+a[/latex] совпадают. Поэтому от набора [latex]f\{x_i\}[/latex] с помощью подходящего выбора [latex]a[/latex] можно перейти к такому набору [latex]f\{x_i’\}[/latex], что все [latex]x_i’\le0[/latex], наименьшие [latex]x_i[/latex] равны нулю, а наибольшие — единице. В дальнейшем мы будем рассматривать только такие наборы. Аналогично, если заменить числа [latex]x_i[/latex] на [latex]1-x_i[/latex], то [latex]y_i[/latex] заменятся на [latex]1-y_i[/latex]. Следовательно, от набора [latex]f\{x_i\}[/latex] можно перейти к набору [latex]f\{1-x_i\}[/latex]: максимальные разности между числами [latex]y_i[/latex] и числами [latex]1-y_i[/latex] одинаковы.

Решим задачу. Пусть [latex]y_k[/latex] — наименьшее, а [latex]y_t[/latex] — наибольшее из чисел [latex]f\{y_i\}[/latex].

Если [latex]k<l[/latex], то [latex]y_l-y_k=\frac{k y_k}{l}+\frac{x_{k+1}+\ldots+x_l}{l}-y_k[/latex][latex]=\frac{x_{k+1}+\ldots+x_l}{l}-\frac{l-k}{l} y_k[/latex][latex]\le\frac{x_{k+1}+\ldots+x_l}{l}\le\frac{l-k}{l}\le1-\frac{k}{l}\le1-\frac{1}{n}[/latex]

Если же [latex]k>l[/latex], то [latex]y_l-y_k=\frac{k-l}{k} y_l-\frac{y_{l+1}+\ldots+y_k}{k}\le1-\frac{l}{k}\le1-\frac{1}{n}[/latex].

Из вышесказанного следует, что максимальная разность не больше [latex]1-\frac{1}{n}[/latex]. Набор с такой разностью можно легко указать: [latex]x_1=0[/latex], [latex]x_2=x_3=\ldots=x_n=1[/latex].

Л. Г. Лиманов
Научно-популярный журнал «Квант», 1974 год, №3, страницы 38-39.

Итог:
Формула, которую необходимо использовать для решения этой задачи, это [latex]D=1-\frac{1}{n}[/latex], где D — наибольшая разность элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n}{n}[/latex], а [latex]n[/latex] — их количество.

Ссылки

Условие задачи (страница 42);
Оригинал кода программы.

Related Images:

КМ26

30/09/2016 by Даниил Юдин

Задача

Задача из журнала «Квант» №6 1970 г.
Предположим, что в каждом номере нашего журнала в задачнике «Кванта» будет пять задач по математике. Обозначим через [latex]f(x, y) [/latex] номер первой из задач [latex]x[/latex]-го номера журнала за [latex]y[/latex]-й год (например, [latex]f (6.1970)=26)[/latex]. Напишите общую формулу для[latex]f(x, y) [/latex]для всех [latex] x , y (1 \le x \le 12 , y \ge 1970) [/latex] .
Решите уравнение [latex]f(x, y)=y [/latex] .

Тесты

Входные данные		Выходные данные
[latex]x [/latex]	[latex]y [/latex]	[latex]f(x, y) [/latex]
6	1970	26
12	1970	56
7	1998	1711
9	2016	2801

Код

#include <iostream>
using namespace std;

int main() {
    int x,y;
    cin>>x>>y;
    cout<<x*5-4+60*(y-1970);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x,y;

cin>>x>>y;

cout<<x*5-4+60*(y-1970);

return 0;

}

Решение задачи

При прочтении условия данной задачи, становится ясно что речь идёт о арифметической последовательности с первым элементом [latex]a_1 = 1 [/latex] и разностью данной последовательности [latex]d = 5 [/latex]. Таким образом для нахождения номера первой задачи из [latex]x [/latex]-го номера за [latex] y [/latex]-ый год требуется формула для нахождения [latex]n[/latex]-го члена прогрессии [latex]a_n=a_1+d(n-1) [/latex]. Но для этого случая нужно вывести [latex]n[/latex] что мы сделаем сложив номер выпуска [latex]x [/latex] и разницу [latex]y-1970[/latex] помноженную на [latex]60[/latex] (что является количеством задач опубликованных за год). Зная всё вышеперечисленное выводим общую формулу [latex]f(x, y) = 1 + 5\*(x-1)+60\*(y-1970)[/latex] . В последствии формула была изменена, что позволило избавиться от лишних действий и слегка сократить формулу. Вид этой формулы: [latex]f(x, y) = 5\*x-4+60\*(y-1970)[/latex] .

Ссылки

Условие задачи.
ideone

Related Images:

Ю11.16

24/10/2014 by Іванов Вячеслав Володимирович

Задача:
Для заданной матрицы [latex]A(n, n)[/latex] найти обратную [latex]A^{-1}[/latex], используя итерационную формулу:
[latex]A_{k}^{-1} = A_{k-1}^{-1}(2E-A A_{k}^{-1}),[/latex] где [latex]E[/latex] — единичная матрица, [latex]A_{0}^{-1} = E[/latex]. Итерационный процесс заканчивается, если для заданной погрешности [latex]\varepsilon[/latex] справедливо:
[latex]\left| det(A A_{k}^{-1})-1 \right| \le \varepsilon[/latex]

Анализ задачи:
Прежде чем приступать к решению средствами языка C++, я создал прототип в системе компьютерной алгебры Wolfram Mathematica, с которым планировал сверяться при тестировании программы. Тем не менее, внимательный анализ показал, что с таким выбором начального приближения процесс уже на пятом шаге в значительной мере расходится даже для матриц размера 2*2. После уточнения условий и анализа дополнительного материала, посвященного методу Ньютона-Шульца, исходное приближение было изменено (по результатам исследования «An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications», Victor Pan, Robert Schreiber, стр. 8):
[latex]A_{0}^{-1} =\frac { A }{ \left\| A \right\|_{1} \left\| A \right\| _{\infty } }[/latex], где [latex]{ \left\| A \right\| }_{ 1 }=\max _{ i }{ \sum _{ j=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } } [/latex], [latex]{ \left\| A \right\| }_{ \infty }=\max _{ j }{ \sum _{ i=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } }[/latex].
Эффективность предложенного подхода иллюстрируют результаты работы прототипа:

Следовательно, из пространства задачи можно переместиться в пространство решения и составить алгоритм реализации предложенного метода на языке C++.

Тесты:

[latex]n[/latex]	[latex]A[/latex]	[latex]A^{-1}[/latex]	Результат
3	1 2 3 5 5 7 11 13 7	-0.964771 0.430661 -0.017183 0.723533 -0.447973 0.137884 0.172358 0.155200 -0.086211	Пройден
2	1 2 2 1	-0.333067 0.666400 0.666400 -0.333067	Пройден
5	1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	Пройден
3	1 2 3 4 5 6 7 8 9	Матрица вырождена	Пройден

Программный код:

#include <cstdio>
#include <algorithm>
#include <cmath>
//очистить выделенную память
void clear(double **arr, int n)
{
    for(int i = 0; i < n; i++)
        delete[] arr[i];
    delete[] arr;
}
//создать копию массива
double** clone(double **arr, int n)
{
    double **newArr = new double*[n];
    for(int row = 0; row < n; row++)
    {
        newArr[row] = new double[n];
        for(int col = 0; col < n; col++)
            newArr[row][col] = arr[row][col];
    }
    return newArr;
}
//print the matrix
void show(double **matrix, int n)
{
    for(int row = 0; row < n; row++){
            for(int col = 0; col < n; col++)
                printf("%lf\t", matrix[row][col]);
            printf("\n");
    }
    printf("\n");
}
//матричное умножение матриц
double** matrix_multi(double **A, double **B, int n)
{
    double **result = new double*[n];
    //заполнение нулями
    for(int row = 0; row < n; row++){
        result[row] = new double[n];
        for(int col = 0; col < n; col++){
            result[row][col] = 0;
        }
    }

    for(int row = 0; row < n; row++){
        for(int col = 0; col < n; col++){
            for(int j = 0; j < n; j++){
                result[row][col] += A[row][j] * B[j][col];
            }
        }
    }
    return result;
}
//умножение матрицы на число
void scalar_multi(double **m, int n, double a){
    for(int row = 0; row < n; row++)
        for(int col = 0; col < n; col++){
            m[row][col] *= a;
        }
}
//вычисление суммы двух квадратных матриц
void sum(double **A, double **B, int n)
{
    for(int row = 0; row < n; row++)
        for(int col = 0; col < n; col++)
            A[row][col] += B[row][col];
}

//вычисление определителя
double det(double **matrix, int n) //квадратная матрица размера n*n
{
    double **B = clone(matrix, n);
    //приведение матрицы к верхнетреугольному виду
    for(int step = 0; step < n - 1; step++)
        for(int row = step + 1; row < n; row++)
        {
            double coeff = -B[row][step] / B[step][step]; //метод Гаусса
            for(int col = step; col < n; col++)
                B[row][col] += B[step][col] * coeff;
        }
    //Рассчитать определитель как произведение элементов главной диагонали
    double Det = 1;
    for(int i = 0; i < n; i++)
        Det *= B[i][i];
    //Очистить память
    clear(B, n);
    return Det;
}

int main()
{
    //Исходная матрица, динамический двухмерный массив
    int n; scanf("%d", &n);
    double **A = new double*[n];
    for(int row = 0; row < n; row++)
    {
        A[row] = new double[n];
            for(int col = 0; col < n; col++)
                scanf("%lf", &A[row][col]);
    }

    /* Численное вычисление обратной матрицы по методу Ньютона-Шульца
        1. Записать начальное приближение [Pan, Schreiber]:
            1) Транспонировать данную матрицу
            2) Нормировать по столбцам и строкам
        2. Повторять процесс до достижения заданной точности.
    */

    double N1 = 0, Ninf = 0; //норма матрицы по столбцам и по строкам
    double **A0 = clone(A, n);       //инициализация начального приближения
    for(size_t row = 0; row < n; row++){
        double colsum = 0, rowsum = 0;
        for(size_t col = 0; col < n; col++){
            rowsum += fabs(A0[row][col]);
            colsum += fabs(A0[col][row]);
        }
        N1 = std::max(colsum, N1);
        Ninf = std::max(rowsum, Ninf);
    }
    //транспонирование
    for(size_t row = 0; row < n - 1; row++){
        for(size_t col = row + 1; col < n; col++)
            std::swap(A0[col][row], A0[row][col]);
    }
    scalar_multi(A0, n, (1 / (N1 * Ninf))); //нормирование матрицы
    //инициализация удвоенной единичной матрицы нужного размера
    double **E2 = new double*[n];
    for(int row = 0; row < n; row++)
    {
        E2[row] = new double[n];
            for(int col = 0; col < n; col++){
                if(row == col)
                    E2[row][col] = 2;
                else
                    E2[row][col] = 0;
            }
    }
    double **inv = clone(A0, n); //A_{0}
    double EPS = 0.001;   //погрешность
    if(det(A, n) != 0){ //если матрица не вырождена
        while(fabs(det(matrix_multi(A, inv, n), n) - 1) >= EPS) //пока |det(A * A[k](^-1)) - 1| >= EPS
        {
            double **prev = clone(inv, n); //A[k-1]
            inv = matrix_multi(A, prev, n);   //A.(A[k-1]^(-1))
            scalar_multi(inv, n, -1);         //-A.(A[k-1]^(-1))
            sum(inv, E2, n);                   //2E - A.(A[k-1]^(-1))
            inv = matrix_multi(prev, inv, n); //(A[k-1]^(-1)).(2E - A.(A[k-1]^(-1)))
            clear(prev, n);
        }
        //вывод матрицы на экран
        show(inv, n);
    }
    else
        printf("Impossible\n");
    clear(A, n);
    clear(E2, n);
    return 0;
}

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

154

155

156

157

158

#include <cstdio>

#include <algorithm>

#include <cmath>

//очистить выделенную память

void clear(double **arr, int n)

{

for(int i = 0; i < n; i++)

delete[] arr[i];

delete[] arr;

}

//создать копию массива

double** clone(double **arr, int n)

{

double **newArr = new double*[n];

for(int row = 0; row < n; row++)

{

newArr[row] = new double[n];

for(int col = 0; col < n; col++)

newArr[row][col] = arr[row][col];

}

return newArr;

}

//print the matrix

void show(double **matrix, int n)

{

for(int row = 0; row < n; row++){

for(int col = 0; col < n; col++)

printf("%lf\t", matrix[row][col]);

printf("\n");

}

printf("\n");

}

//матричное умножение матриц

double** matrix_multi(double **A, double **B, int n)

{

double **result = new double*[n];

//заполнение нулями

for(int row = 0; row < n; row++){

result[row] = new double[n];

for(int col = 0; col < n; col++){

result[row][col] = 0;

}

for(int row = 0; row < n; row++){

for(int col = 0; col < n; col++){

for(int j = 0; j < n; j++){

result[row][col] += A[row][j] * B[j][col];

}

return result;

}

//умножение матрицы на число

void scalar_multi(double **m, int n, double a){

for(int row = 0; row < n; row++)

for(int col = 0; col < n; col++){

m[row][col] *= a;

}

//вычисление суммы двух квадратных матриц

void sum(double **A, double **B, int n)

{

for(int row = 0; row < n; row++)

for(int col = 0; col < n; col++)

A[row][col] += B[row][col];

}

//вычисление определителя

double det(double **matrix, int n) //квадратная матрица размера n*n

{

double **B = clone(matrix, n);

//приведение матрицы к верхнетреугольному виду

for(int step = 0; step < n - 1; step++)

for(int row = step + 1; row < n; row++)

{

double coeff = -B[row][step] / B[step][step]; //метод Гаусса

for(int col = step; col < n; col++)

B[row][col] += B[step][col] * coeff;

}

//Рассчитать определитель как произведение элементов главной диагонали

double Det = 1;

for(int i = 0; i < n; i++)

Det *= B[i][i];

//Очистить память

clear(B, n);

return Det;

}

int main()

{

//Исходная матрица, динамический двухмерный массив

int n; scanf("%d", &n);

double **A = new double*[n];

for(int row = 0; row < n; row++)

{

A[row] = new double[n];

for(int col = 0; col < n; col++)

scanf("%lf", &A[row][col]);

}

/* Численное вычисление обратной матрицы по методу Ньютона-Шульца

1. Записать начальное приближение [Pan, Schreiber]:

1) Транспонировать данную матрицу

2) Нормировать по столбцам и строкам

2. Повторять процесс до достижения заданной точности.

double N1 = 0, Ninf = 0; //норма матрицы по столбцам и по строкам

double **A0 = clone(A, n); //инициализация начального приближения

for(size_t row = 0; row < n; row++){

double colsum = 0, rowsum = 0;

for(size_t col = 0; col < n; col++){

rowsum += fabs(A0[row][col]);

colsum += fabs(A0[col][row]);

}

N1 = std::max(colsum, N1);

Ninf = std::max(rowsum, Ninf);

}

//транспонирование

for(size_t row = 0; row < n - 1; row++){

for(size_t col = row + 1; col < n; col++)

std::swap(A0[col][row], A0[row][col]);

}

scalar_multi(A0, n, (1 / (N1 * Ninf))); //нормирование матрицы

//инициализация удвоенной единичной матрицы нужного размера

double **E2 = new double*[n];

for(int row = 0; row < n; row++)

{

E2[row] = new double[n];

for(int col = 0; col < n; col++){

if(row == col)

E2[row][col] = 2;

else

E2[row][col] = 0;

}

double **inv = clone(A0, n); //A_{0}

double EPS = 0.001; //погрешность

if(det(A, n) != 0){ //если матрица не вырождена

while(fabs(det(matrix_multi(A, inv, n), n) - 1) >= EPS) //пока |det(A * A[k](^-1)) - 1| >= EPS

{

double **prev = clone(inv, n); //A[k-1]

inv = matrix_multi(A, prev, n); //A.(A[k-1]^(-1))

scalar_multi(inv, n, -1); //-A.(A[k-1]^(-1))

sum(inv, E2, n); //2E - A.(A[k-1]^(-1))

inv = matrix_multi(prev, inv, n); //(A[k-1]^(-1)).(2E - A.(A[k-1]^(-1)))

clear(prev, n);

}

//вывод матрицы на экран

show(inv, n);

}

else

printf("Impossible\n");

clear(A, n);

clear(E2, n);

return 0;

}

Программа доступна для тестирования по ссылке: http://ideone.com/7YphoX.

Алгоритм решения
При решении данной задачи оправдывает себя подход «разделяй и властвуй»: вычисление обратной матрицы подразумевает промежуточные этапы, корректной реализации которых следует уделить особое внимание. Наверняка стоило бы написать класс matrix и реализовать перегрузку операций, но задачу можно решить и без применения объектно-ориентированных средств, пусть от этого решение и потеряет в изящности.
Можно выделить следующие подзадачи:

Инициализация динамического двухмерного массива и передача его в функцию.
Вычисление определителя матрицы (с применением метода Гаусса).
Вычисление нормы матрицы.
Транспонирование матрицы.
Умножение матрицы на скаляр.
Матричное умножение матриц.
Сложение двух матриц.
Непосредственно итерационный процесс Ньютона-Шульца

Ниже приведено пояснение к подходу к реализации некоторых подзадач:

Выделение памяти для хранения массива происходит не на этапе запуска программы, после компиляции. Для инициализации использован конструктор new
Вычисление определителя можно разбить на два последовательных шага:
1. Приведение матрицы к верхнетреугольному виду (методом Гаусса).
2. Вычисление определителя как произведения элементов главной диагонали.
Нормы матрицы вычисляются как максимальные значения суммы элементов по столбцам и строкам соответственно.
При транспонировании обмениваются местами элементы, симметричные главной диагонали.
При умножении матрицы на скаляр каждый элемент матрицы умножается на соответствующее вещественное число.
При перемножении двух квадратных матриц используется промежуточный массив для хранения результата вычислений.
Сложение двух матриц аналогично попарному сложению элементов, расположенных на соответствующих позициях.
Максимально допустимая погрешность для метода Ньютона-Шульца [latex]\varepsilon = 0.001[/latex]. Программа использует локальный массив для хранения [latex]A_{k}^{-1}[/latex], инициализация которого происходит в теле цикла.

Технические детали реализации:
При выполнении подзадач часто приходится использовать локальные массивы, так что для очистки выделенной под них памяти создана отдельная функция clear().

Related Images:

Ю11.12

21/10/2014 by Бронфен-Бова Роман

Задача:
Интерполяционный многочлен Лагранжа. Значения функции [latex]y=f\left(x\right)[/latex] заданы таблично в массиве [latex]Y\left(x\right)[/latex] при соответствующих значениях аргумента в упорядоченном массиве [latex]X\left(x\right)[/latex]. Найти значение функции в произвольной точке [latex]x[/latex] по формуле Лагранжа:
[latex]y={L}_{n}\left(x\right)=\sum _{i=1}^{n}{{y}_{i}\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}}[/latex]

Вводимые значения:

X:	-1	0	1	2
Y:	1	2	3	-1

Код программы:

#include <iostream>
#include <vector>
using namespace std;

double LP(double x, vector<double> xv, vector<double> yv) { //Lagrange polynomial
	int size = xv.size(); //Количество точек (для удобства)
	double sum = 0; //Значение функции
	for(int i = 0; i < size; i++){
		double mul = 1; //Произведение
		for(int j = 0; j < size; j++){
			if(i!=j) mul *= (x - xv[j])/(xv[i]-xv[j]);
		}
		sum += yv[i]*mul;
	}
	return sum;
}

int main() {
	int counter = 0;
	double a = -3; //Левая грань
	double b = 3; //Правая грань
	int fragments = 101; //Разбиение
	vector<double> xv {};
	vector<double> yv {};
	double inp;
	while(cin >> inp) counter++%2 ? yv.push_back(inp) : xv.push_back(inp); //Заполнение
	for(int i = 0; i < fragments; i++){
		double x = a + (b-a)/(fragments-1)*i;
		printf("%6.3lf\t%6.3lf\n", x, LP(x, xv, yv));
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

double LP(double x, vector<double> xv, vector<double> yv) { //Lagrange polynomial

int size = xv.size(); //Количество точек (для удобства)

double sum = 0; //Значение функции

for(int i = 0; i < size; i++){

double mul = 1; //Произведение

for(int j = 0; j < size; j++){

if(i!=j) mul *= (x - xv[j])/(xv[i]-xv[j]);

}

sum += yv[i]*mul;

}

return sum;

}

int main() {

int counter = 0;

double a = -3; //Левая грань

double b = 3; //Правая грань

int fragments = 101; //Разбиение

vector<double> xv {};

vector<double> yv {};

double inp;

while(cin >> inp) counter++%2 ? yv.push_back(inp) : xv.push_back(inp); //Заполнение

for(int i = 0; i < fragments; i++){

double x = a + (b-a)/(fragments-1)*i;

printf("%6.3lf\t%6.3lf\n", x, LP(x, xv, yv));

}

return 0;

}

Код программы на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
 
	static double LP(double x, double[] xv, double[] yv){
		int size = xv.length;
		double sum = 0;
		for(int i = 0; i < size; i++){
			double mul = 1;
			for(int j = 0; j < size; j++){
				if(i != j){
					mul *= (x-xv[j])/(xv[i]-xv[j]);
				}
			}
			sum += yv[i]*mul;
		}
		return sum;
	}
 
	static Scanner sc = new Scanner(System.in);
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int counter = 0;
		double a = -3;
		double b = 3;
		int fragments = 101;
		ArrayList<Double> xvinp = new ArrayList<Double>();
		ArrayList<Double> yvinp = new ArrayList<Double>();
		double[] xv;
		double[] yv;
		while(sc.hasNext()){
			double inp = sc.nextDouble();
			if(counter%2 == 0){
				xvinp.add(inp);
			}else{
				yvinp.add(inp);
			}
			counter++;
		}
		xv = new double[xvinp.size()];
		yv = new double[yvinp.size()];
		for(int i = 0; i < xvinp.size(); i++){
			xv[i] = xvinp.get(i);
			yv[i] = yvinp.get(i);
		}
		for(int i = 0; i < fragments; i++){
			double x = a + (b-a)/(fragments-1)*i;
			System.out.println(x + "\t" + LP(x, xv, yv));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static double LP(double x, double[] xv, double[] yv){

int size = xv.length;

double sum = 0;

for(int i = 0; i < size; i++){

double mul = 1;

for(int j = 0; j < size; j++){

if(i != j){

mul *= (x-xv[j])/(xv[i]-xv[j]);

}

sum += yv[i]*mul;

}

return sum;

}

static Scanner sc = new Scanner(System.in);

public static void main (String[] args) throws java.lang.Exception

{

int counter = 0;

double a = -3;

double b = 3;

int fragments = 101;

ArrayList<Double> xvinp = new ArrayList<Double>();

ArrayList<Double> yvinp = new ArrayList<Double>();

double[] xv;

double[] yv;

while(sc.hasNext()){

double inp = sc.nextDouble();

if(counter%2 == 0){

xvinp.add(inp);

}else{

yvinp.add(inp);

}

counter++;

}

xv = new double[xvinp.size()];

yv = new double[yvinp.size()];

for(int i = 0; i < xvinp.size(); i++){

xv[i] = xvinp.get(i);

yv[i] = yvinp.get(i);

}

for(int i = 0; i < fragments; i++){

double x = a + (b-a)/(fragments-1)*i;

System.out.println(x + "\t" + LP(x, xv, yv));

}

Идея решения:
Использование отдельной функции, которой надо передать 3 параметра: значение аргумента, массив исходных значений аргумента и массив исходных значений функции при соответствующих аргументах. Эта функция возвращает значение многочлена Лагранжа при подстановки вместо [latex]x[/latex] конкретного значения.

В функции был использован внешний цикл for для вычисления суммы в формуле и внутренний цикл for для вычисления произведения [latex]\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}[/latex].

В программе мы разбиваем отрезок [-3, 3] на 101 отдельную точку и вычисляем значение полинома Лагранжа для каждой из этих точек. Выводим на экран.

График:

Комментарии: Точки выбраны специально. Мне просто захотелось увидеть, как выглядит график функции, которую мы разбирали на паре (кстати по той же самой теме =) ). График сделан в xls. Векторы выбраны по причине ограниченности массива.

Related Images:

Ю3.39

12/10/2014 by Бронфен-Бова Роман

Задача: Численно убедиться в справедливости равенства [latex]\frac{1}{4}\ln{\frac{1+x}{1-x}}+\frac{1}{2}\arctan{x}=\quad x+\frac{{x}^{5}}{5}+\dots+\frac{{x}^{4n+1}}{4n+1}+\dots[/latex], для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]e[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex]n[/latex] слагаемых, необходимых, для достижения заданной точности. Интервал для этой задачи: [latex]-1<x<1[/latex].

Ввод		Вывод
[latex]x[/latex]	Погрешность	Output	Комментарий
-0.99	1e-4	148	Пройден
0.99	1e-4	148	Пройден
0.99	1e-14	685	Пройден
0.7	1e-10	14	Пройден
-0.3	1e-13	6	Пройден
0.001	1e-13	1	Пройден

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	double x, e; //Переменная и погрешность
	scanf("%lf %le", &x, &e);
	double curr = 1./4.*log((1.+x)/(1.-x)) + (1./2.)*atan(x);  //Левая часть выражения
	int count = 0; //Счетчик
	double y = x; //i-тое слагаемое
	double sum = x; //Сумма
	for(; fabs(sum-curr) > e; count++){
		double n = (4.*count+1.)/(4.*count+5.);
		y = y*x*x*x*x*n;
		sum += y;
	}
	count++;
	printf("%d", count);
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double x, e; //Переменная и погрешность

scanf("%lf %le", &x, &e);

double curr = 1./4.*log((1.+x)/(1.-x)) + (1./2.)*atan(x); //Левая часть выражения

int count = 0; //Счетчик

double y = x; //i-тое слагаемое

double sum = x; //Сумма

for(; fabs(sum-curr) > e; count++){

double n = (4.*count+1.)/(4.*count+5.);

y = y*x*x*x*x*n;

sum += y;

}

count++;

printf("%d", count);

return 0;

}

Идея решения: Используем цикл for, в условие которого ставим проверку на превышение погрешности суммы. Левую часть выражения вычисляем и записываем в переменную [latex]curr[/latex]. Сумму (то что стоит в правой части выражения) объявим как [latex]sum[/latex], и инициализируем значением [latex]x[/latex] (Это делается для того, чтобы во время работы цикла не вычислялось одно лишнее слагаемое).

Каждую итерацию цикла инкрементируем счетчик [latex]count[/latex]. Переменную [latex]y[/latex], которая соответствует i-тому слагаемому суммы, увеличивают до значения следующего слагаемого и прибавляют к сумме. Далее проверяем разность частичной суммы и заданного значения [latex]curr[/latex]. Если эта разность будет удовлетворять нашей точности, то число [latex]count[/latex] и будет количеством слагаемых в правой части.

Замечание: После цикла значение [latex]count[/latex] вновь инкрементируется, это сделано по следующей причине: сумма изначально содержала в себе первое слагаемое. Если сумма бы изначально содержала в себе 0, то нам пришлось бы вычислять лишнее слагаемое.

Ideone

Related Images:

Ю3.17

09/10/2014 by Бронфен-Бова Роман

Задача: Сколько сомножителей надо взять в произведении: [latex]\prod_{k=1}^{\infty}{(1+\frac{{(-1)}^{k}}{2k+1})}=\frac{\sqrt{2}}{2}[/latex], чтобы равенство выполнялось до шестой значащей цифры, то есть с погрешностью не более [latex]{10}^{-6}[/latex]

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	double curr = sqrt(2.0)/2; //Переменная для сравнения
	double mul = 1;   //Произведение
	double e = 1.0e-6;  //Точность
	int count = 1; //Счетчик
	for(;fabs(mul - curr) > e;count++){
		mul *= (1. + (count % 2 ? (-1) : 1)/(2.*count + 1));
	}
	printf("%d",count); 
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double curr = sqrt(2.0)/2; //Переменная для сравнения

double mul = 1; //Произведение

double e = 1.0e-6; //Точность

int count = 1; //Счетчик

for(;fabs(mul - curr) > e;count++){

mul *= (1. + (count % 2 ? (-1) : 1)/(2.*count + 1));

}

printf("%d",count);

return 0;

}

Идея решения: Используем цикл for, в качестве [latex]k[/latex] в формуле используем переменную [latex]count[/latex] в программе. Переменную, которая будет соответствовать произведению, назовем [latex]mul[/latex] (сокращенно от multiplication) и присвоим ей значение 1 как нейтральный элемент для операции умножения. Каждую итерацию цикла проверяем разность [latex]mul-curr[/latex], где [latex]curr=\frac{\sqrt{2}}{2}[/latex], на превышение погрешности [latex]{10}^{-6}[/latex].

Если разность больше точности, умножаем [latex]mul[/latex] на выражение под знаком произведения и увеличиваем [latex]count[/latex] на единицу.

Если разность меньше точности, число [latex]count[/latex] и будет количеством сомножителей в произведении.

Число сомножителей оказалось достаточно большим — 88390. Ideone

Related Images:

А52

03/10/2014 by Бровко Ілля

Задача. Даны действительный числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex], [latex]s[/latex], [latex]t[/latex], [latex]u[/latex]([latex]s[/latex] и [latex]t[/latex] одновременно не равны нулю). Известно, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] не лежат на прямой [latex]l[/latex], заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] разбивает координатную плоскость на две полуплоскости. Выяснить, верно ли, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] принадлежат разным полуплоскостям.

В этой задаче надо воспользоваться тем, что две точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на прямой, определяемой уравнением [latex]sx + ty + u = 0[/latex], принадлежат одной полуплоскости, если [latex]sa + tb + u[/latex] и [latex]sc + td + u[/latex] – числа одного знака. Справедлив и более общий факт: если уравнение [latex]F(x, y) = 0[/latex] определяет прямую или кривую, разбивающую координатную плоскость на две части, то точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на этой линии, принадлежат одной и той же части плоскости, если [latex]F(a, b)[/latex] и [latex]F(c, d)[/latex]– числа одного знака.

a	b	c	d	s	t	u	Ответ
5	-4	2	9	6	-3	7	Обе точки принадлежат разным полуплоскостям.
-5	-4	-6	-3	2	7	-1	Обе точки принадлежат одной полуплоскости.
-5	-4	-6	-3	0	0	-1	Условие некорректно:s и t не должны одновременно равняются нулю.
4	7	2	1	-4	3	-5	Одна, либо обе из точек лежат на прямой, соответственно не принадлежат ни одной из полуплоскостей.

В программу вводятся исходные данные, среди которых координаты точек [latex](a, b)[/latex] и [latex](c, d)[/latex]. Если набор значений будет таким, что выполнится уравнение прямой [latex]sx+ty+u=0[/latex], (где x— a и d. А y— b и d), то это значит, что одни из точек (или сразу две) принадлежат прямой и следовательно не принадлежат ни одной из полуплоскостей. Если результаты уравнений [latex](s*a)+(t*b)+u[/latex] и [latex](s*c)+(t*d)+u[/latex]- числа одного знака, то точки лежат в одной полуплоскости. Если же эти числа разного знака, то обе точки принадлежат разным полуплоскостям.

Код на C++:

#include <iostream>
#include <math.h>
using namespace std;

int main() 
{
	double a,b,c,d,s,t,u,R,K;
		scanf("%lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&s,&t,&u);
	if (s==0.00 && t==0.00)
	{
		printf ("Условие некорректно:s и t не должны одновременно равняются нулю. \n");
	}
	else
	{
		R=(s*a)+(t*b)+u;
		K=(s*c)+(t*d)+u;
		if (R==0.00 || K==0.00)
		{
			printf ("Одна, либо обе из точек лежат на прямой, соответственно не принадлежит ни одной из полуплоскостей. \n");
		}
		else if ((R>0.00 && K>0.00) || (R<0.00 && K<0.00))
		{
			printf ("Обе точки принадлежат одной полуплоскости. \n");
		}
		else
		{
			(R>0.00 && K<0.00) || (R<0.00 && K>0.00);
				printf ("Обе точки принадлежат разным полуплоскостям. \n");
		}
	}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

double a,b,c,d,s,t,u,R,K;

scanf("%lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&s,&t,&u);

if (s==0.00 && t==0.00)

{

printf ("Условие некорректно:s и t не должны одновременно равняются нулю. \n");

}

else

{

R=(s*a)+(t*b)+u;

K=(s*c)+(t*d)+u;

if (R==0.00 || K==0.00)

{

printf ("Одна, либо обе из точек лежат на прямой, соответственно не принадлежит ни одной из полуплоскостей. \n");

}

else if ((R>0.00 && K>0.00) || (R<0.00 && K<0.00))

{

printf ("Обе точки принадлежат одной полуплоскости. \n");

}

else

{

(R>0.00 && K<0.00) || (R<0.00 && K>0.00);

printf ("Обе точки принадлежат разным полуплоскостям. \n");

}

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Brovko
{
	public static void main (String[] args) throws java.lang.Exception
	{
	double a,b,c,d,s,t,u,R,K;
	Scanner in = new Scanner(System.in);
	a=in.nextDouble();
	b=in.nextDouble();
	c=in.nextDouble();
	d=in.nextDouble();
	s=in.nextDouble();
	t=in.nextDouble();
	u=in.nextDouble();
	if (s==0 && t==0)
	{
		System.out.printf("Условие некорректно:s и t не должны одновременно равняются нулю. \n");
	}
	else
	{
		R=(s*a)+(t*b)+u;
		K=(s*c)+(t*d)+u;
		if (R==0 || K==0)
		{
			System.out.printf ("Одна, либо обе из точек лежат на прямой, соответсвенно не пренадлежит ни одной из полуплоскостей. \n");
		}
		else if ((R>0 && K>0) || (R<0 && K<0))
		{
			System.out.printf ("Обе точки принадлежат одной полуплоскости. \n");
		}
		else
		{
			if((R>0 && K<0) || (R<0 && K>0));
			{
				System.out.printf ("Обе точки принадлежат разным полуплоскостям. \n");
			}
		}
	}
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Brovko

{

public static void main (String[] args) throws java.lang.Exception

{

double a,b,c,d,s,t,u,R,K;

Scanner in = new Scanner(System.in);

a=in.nextDouble();

b=in.nextDouble();

c=in.nextDouble();

d=in.nextDouble();

s=in.nextDouble();

t=in.nextDouble();

u=in.nextDouble();

if (s==0 && t==0)

{

System.out.printf("Условие некорректно:s и t не должны одновременно равняются нулю. \n");

}

else

{

R=(s*a)+(t*b)+u;

K=(s*c)+(t*d)+u;

if (R==0 || K==0)

{

System.out.printf ("Одна, либо обе из точек лежат на прямой, соответсвенно не пренадлежит ни одной из полуплоскостей. \n");

}

else if ((R>0 && K>0) || (R<0 && K<0))

{

System.out.printf ("Обе точки принадлежат одной полуплоскости. \n");

}

else

{

if((R>0 && K<0) || (R<0 && K>0));

{

System.out.printf ("Обе точки принадлежат разным полуплоскостям. \n");

}

С программой можно ознакомится тут (C++)/тут (Java).

Related Images:

Ю1.9

21/09/2014 by Марченко Філіп Олександрович

Кубическое уравнение. Заданы три корня кубического уравнения : [latex]x_{1},x_{2},x_{3}[/latex] . Найти коэффициенты этого уравнения.

[latex] x_{1}[/latex]	[latex] x_{2}[/latex]	[latex] x_{3}[/latex]	Результат [latex]b[/latex]	Результат [latex] c[/latex]	Результат [latex] d[/latex]	Комментарий:
1	2	3	-6.00	11.00	-6.00	Тест пройден
0.5	6	0.78	-7.28	8.07	-2.34	Тест пройден
-1	-2	-2.25	5.25	8.75	4.50	Тест пройден
-0.24	-1	2.24	-1.00	-2.54	-0,54	Тест пройден

#include <iostream>
using namespace std;

int main () {
	double x1, x2, x3;
	scanf ( " %lf %lf %lf ", &x1, &x2, &x3 ); // чтение из стандартного потока ввода.
	double b = -( x1 + x2 + x3 ); // вычисление коэф. b, c, d кубического уравнения.
	double c = x1*x2 + x2*x3 + x3*x1;
	double d = -( x1 * x2 * x3 );
	printf ("b = %2.2lf, c = %2.2lf, d = %2.2lf.", b, c, d); //вывод результата.
	return 0;
}

#include <iostream>

using namespace std;

int main () {

double x1, x2, x3;

scanf ( " %lf %lf %lf ", &x1, &x2, &x3 ); // чтение из стандартного потока ввода.

double b = -( x1 + x2 + x3 ); // вычисление коэф. b, c, d кубического уравнения.

double c = x1*x2 + x2*x3 + x3*x1;

double d = -( x1 * x2 * x3 );

printf ("b = %2.2lf, c = %2.2lf, d = %2.2lf.", b, c, d); //вывод результата.

return 0;

}

Дано кубическое уравнение типа [latex](x — x_{1})(x-x_{2})(x-x_{3})=0[/latex]. После недолгих преобразований я получаю такое выражение:

[latex]x^{3}-(x_{1}+x_{2}+x_{3})x^{2}+(x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{1})x-x_{1}x_{2}x_{3}=0[/latex].

Потом присваиваю трём переменным выражения для коэффициентов:

[latex]\begin{cases} & \ x_{1}+x_{2}+x_{3}=-b \\ & \ x_{1}*x_{2}+x_{2}*x_{3}+x_{1}*x_{3}= c \\ & \ x_{1}*x_{2}*x_{3}=-d \end{cases}[/latex]

где [latex]b[/latex] — коэффициент при [latex]x^{2}[/latex], [latex] c[/latex] — при [latex]x[/latex], а [latex] d[/latex] — свободный коэффициент.

В итоге, все решение задачи свернулось в 3 этапа:

Ввод переменных.
Вычисление коэффициентов.
Вывод результата.

Результат выводится с точностью до двух знаков после запятой.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A {
	public static void main (String [] args){
		double x1, x2, x3;
		Scanner sc = new Scanner (System.in);
		x1 = sc.nextDouble();
		x2 = sc.nextDouble();
		x3 = sc.nextDouble();
		double b = -( x1 + x2 + x3 ); 
		double c = (x1*x2 + x2*x3 + x3*x1);
		double d = -( x1 * x2 * x3 );
		System.out.println (b);
		System.out.println (c);
		System.out.println (d);
	}	
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A {

public static void main (String [] args){

double x1, x2, x3;

Scanner sc = new Scanner (System.in);

x1 = sc.nextDouble();

x2 = sc.nextDouble();

x3 = sc.nextDouble();

double b = -( x1 + x2 + x3 );

double c = (x1*x2 + x2*x3 + x3*x1);

double d = -( x1 * x2 * x3 );

System.out.println (b);

System.out.println (c);

System.out.println (d);

}

Related Images:

Ю1.5

19/09/2014 by Бронфен-Бова Роман

Задача: в такси одновременно сели три пассажира. Когда вышел первый пассажир, на счетчике было [latex]p_{1}[/latex] рублей; когда вышел второй — [latex]p_{2}[/latex] рублей. Сколько должен был заплатить каждый пассажир, если по окончании поездки счетчик показал [latex]p_{3}[/latex] рублей? Плата за посадку составляет [latex]p_{0}[/latex] рублей.

Ввод				Вывод
[latex]p_{0}[/latex]	[latex]p_{1}[/latex]	[latex]p_{2}[/latex]	[latex]p_{3}[/latex]	[latex]op_{1}[/latex]	[latex]op_{2}[/latex]	[latex]op_{3}[/latex]	Комментарий
0	0	0	0	0.00	0.00	0.00	Пройден
6	1	2	3	2.33	2.83	3.83	Пройден
7	2	5	16	3.00	4.50	15.50	Пройден
1	1	1	1	0,67	0,67	0,67	Пройден
150	1138	2590	5788	429.33	1155.33	4353.33	Пройден
3	0	0	6	1.00	1.00	7.00	Пройден

[latex]p_{0}[/latex], [latex]p_{1}[/latex], [latex]p_{2}[/latex], [latex]p_{3}[/latex] — целые числа, хоть и определены как double, всё равно это целые числа. У таксиста просто такой счетчик.

#include <iostream>

int main() {
	double p0, p1, p2, p3;		//Поездка
	double op1, op2, op3; 		//Оплата
	
	scanf("%lf %lf %lf %lf", &p0, &p1, &p2, &p3);
	
	op1 = p0/3 + p1/3;
	op2 = p0/3 + p1/3 + (p2-p1)/2;
	op3 = p0/3 + p1/3 + (p2-p1)/2 + (p3-p2);
	
	printf("Первый заплатил %5.3lf\n",op1);	
	printf("Второй заплатил %5.3lf\n",op2);
	printf("Третий заплатил %5.3lf\n",op3);
	
	return 0;
}

#include <iostream>

int main() {

double p0, p1, p2, p3; //Поездка

double op1, op2, op3; //Оплата

scanf("%lf %lf %lf %lf", &p0, &p1, &p2, &p3);

op1 = p0/3 + p1/3;

op2 = p0/3 + p1/3 + (p2-p1)/2;

op3 = p0/3 + p1/3 + (p2-p1)/2 + (p3-p2);

printf("Первый заплатил %5.3lf\n",op1);

printf("Второй заплатил %5.3lf\n",op2);

printf("Третий заплатил %5.3lf\n",op3);

return 0;

}

Идея решение: Первый участок проехали трое и расходы делятся на троих ([latex]\frac { { p }_{ 1 } }{ 3 }[/latex]). Второй участок – двое, значит за него двое платят поровну ([latex]\frac{{p}_{2}-{p}_{1}}{2}[/latex]). Последний участок проехал один, ему за него и платить ([latex]{p}_{3}-{p}_{2}[/latex]). Оплатой за поездку для каждого является сумма стоимости каждого пути до его остановки.