e-olymp 7258. Числовые операции

12/04/2021 by Філіпенко Микита

Условие

На доске записано число $1$. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу $1$, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.

Задание
Напишите программу, которая для заданного натурального числа определяет, за какое наименьшее число операций Петя может, начав с единицы, дойти до этого числа.

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

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4),$ которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих $T$ строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

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

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

Тесты

№

Ввод

Вывод

955

4

137

318

3028

300

39

40

71

50

Код

#include <iostream>

using namespace std;

int nonzero(int number) //функция, которая считает количество цифр, не равных нулю, кроме последней
{
  int count = 0;
  number /= 10;
  while (number != 0) {
    if (number % 10 != 0) count++;
    number /= 10;
  }
  return count;
}
int summa(int number) //функция, которая возвращает сумму цифр числа
{
  int sum = 0;
  while (number != 0) {
    sum += number % 10;
    number /= 10;
  }
  return sum;
}
bool edinica(int number) //функция, которая проверяет есть ли среди цифр числа, кроме последней, единица
{
  number /= 10;
  bool ok = false;
  while (number != 0) {
    if (number % 10 == 1) ok = true;
    number /= 10;
  }
  return ok;
}
int kol_vo(int number) //функция, вычисляющая кол-во цифр числа
{
  int count = 0;
  while (number != 0) {
    count++;
    number /= 10;
  }
  return count;
}
int formula(int number) //формула, по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа
{
  int a = kol_vo(number);
  return (5 * a - 1) * (a - 1);
}

int main() {
  //инициализируем переменную t и считываем ее с клавиатуры
  int t;
  cin >> t;
  //инициализируем переменную ni и задаем цикл, который будет работать пока мы вводим значения ni и t>0
  int ni;
  while (cin >> ni and t > 0) {
    //кладем в переменную kol_vo1 значение функции kol_vo от значения ni
    int kol_vo1 = kol_vo(ni);
    //появляется необходимость создать переменную, которая будет равна значению ni,так как с этим значением
    //в дальнейшем будут проводится операции, а в конце программы нам нужно будет обратиться к исходному значению ni 
    int a = ni;
    //задаем массив, размерность которого равна кол-ву цифр числа
    int b[kol_vo1];
    for (int i = 0; i < kol_vo1; i++) {
      b[i] = a % 10;
      a /= 10;
    }
    //далее производим проверку условия №2,которое описано в решении. Если число проходит условие, то 
    //выводим соответствующую формулу, указанную в условии №2
    bool ok = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] == 0) ok = true;
      else {
        ok = false;
        break;
      }
    }
    if (b[kol_vo1 - 1] > 1 and ok == true) {
      cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;
    }
    //далее производим проверку условия №1,которое описано в решении. Если число проходит условие, то 
    //выводим соответствующую формулу, указанную в условии №1
    bool ok2 = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] != 0) ok2 = true;
    }
    if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;
    //остались крайние случаи, когда число однозначное или кратное 10^n.Проверяем число на эти условия
    //и если оно является таковым, выводим соответствующие значения
    if (kol_vo1 == 1) cout << ni - 1 << endl;
    if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;
    //декрементируем переменную t
    t--;
  }
}

#include <iostream>

using namespace std;

int nonzero(int number) //функция, которая считает количество цифр, не равных нулю, кроме последней

{

int count = 0;

number /= 10;

while (number != 0) {

if (number % 10 != 0) count++;

number /= 10;

}

return count;

}

int summa(int number) //функция, которая возвращает сумму цифр числа

{

int sum = 0;

while (number != 0) {

sum += number % 10;

number /= 10;

}

return sum;

}

bool edinica(int number) //функция, которая проверяет есть ли среди цифр числа, кроме последней, единица

{

number /= 10;

bool ok = false;

while (number != 0) {

if (number % 10 == 1) ok = true;

number /= 10;

}

return ok;

}

int kol_vo(int number) //функция, вычисляющая кол-во цифр числа

{

int count = 0;

while (number != 0) {

count++;

number /= 10;

}

return count;

}

int formula(int number) //формула, по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа

{

int a = kol_vo(number);

return (5 * a - 1) * (a - 1);

}

int main() {

//инициализируем переменную t и считываем ее с клавиатуры

int t;

cin >> t;

//инициализируем переменную ni и задаем цикл, который будет работать пока мы вводим значения ni и t>0

int ni;

while (cin >> ni and t > 0) {

//кладем в переменную kol_vo1 значение функции kol_vo от значения ni

int kol_vo1 = kol_vo(ni);

//появляется необходимость создать переменную, которая будет равна значению ni,так как с этим значением

//в дальнейшем будут проводится операции, а в конце программы нам нужно будет обратиться к исходному значению ni

int a = ni;

//задаем массив, размерность которого равна кол-ву цифр числа

int b[kol_vo1];

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

b[i] = a % 10;

a /= 10;

}

//далее производим проверку условия №2,которое описано в решении. Если число проходит условие, то

//выводим соответствующую формулу, указанную в условии №2

bool ok = false;

for (int i = 0; i < kol_vo1 - 1; i++) {

if (b[i] == 0) ok = true;

else {

ok = false;

break;

}

if (b[kol_vo1 - 1] > 1 and ok == true) {

cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;

}

//далее производим проверку условия №1,которое описано в решении. Если число проходит условие, то

//выводим соответствующую формулу, указанную в условии №1

bool ok2 = false;

for (int i = 0; i < kol_vo1 - 1; i++) {

if (b[i] != 0) ok2 = true;

}

if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;

//остались крайние случаи, когда число однозначное или кратное 10^n.Проверяем число на эти условия

//и если оно является таковым, выводим соответствующие значения

if (kol_vo1 == 1) cout << ni - 1 << endl;

if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;

//декрементируем переменную t

t--;

}

Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и так далее, пока количество цифр в числе не будет таким, какое требуется.
Наименьшее количество операций, необходимое для того, чтобы перейти от числа $10^{n-1}$ до заданного $n$ -значного числа $N$ можно посчитать следующим образом:
1. Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то количество операций можно посчитать по формуле summa(N) + nonzero(N) – edinica(N) - 1, где summa(N) — сумма цифр числа, nonzero(N) — количество цифр, отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N) — число, которое равно единице, если хотя бы на одной позиции числа $N$, кроме последней, есть единица, или равна нулю, если единиц на этих позициях нет.
2. Если все цифры числа $N$, кроме первой, нулевые, а первая цифра больше единицы, то количество операций можно посчитать по формуле summa(N-1)+nonzero(N-1) – edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$ -заданное число, число $n$ -количество цифр числа $N$. Если $n=1$, $N=7$, то для того, чтобы дойти от единицы до заданного числа, потребуется $N-1$ операций. В нашем случае $6$ операций
($1+1=2,
2+1=3,
…
6+1=7$)
Если $n\geq2$, то для этого достаточно привести пример цепочки, подсчитывающая количество операций, которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. $N \Rightarrow 10^{n-1}$. За одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так, чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1. Если $N=10^{n-1}$, то количество операций равно summa(N) + nonzero(N) - edinica(N) - 1 $= $ $0$.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2. Если $N!=10^{n-1}$ и первая цифра числа $N$ равна единице, то проводим следующие операции:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем, далее переставим местами последнюю цифру с какой-нибудь другой, отличной от нуля, кроме первой, и опять отнимем количество единиц, чтобы последняя цифра стала нулевой. Повторять будем до тех пор, пока все цифры, кроме первой, не станут нулями.
Например, возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Количество операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3. Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа, кроме последней, есть единица, то проводим следующие операции:
Сначала уменьшаем последнюю цифру, пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой цифры. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4. Если ни на одной из позиций числа $N$, кроме, возможно, последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра, кроме первой, то проводим следующие операции:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой, кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5. Если первая цифра числа $N$ больше единицы, а все другие цифры — нулевые, то проводим следующие операции:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее написанных алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6. Подсчет операций от $1$ до $10^{n-1}$.
Для того, чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) – edinica(k) - 1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где $n > 1$.
Если $n=1$, то количество операций $= 10 \cdot n – 2 =8$.

Количество операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- количество цифр заданного числа.

Ссылки

Related Images:

e-olymp 6941. Сумма НОД

22/12/2020 by Натан Чачко

Задача

Для заданных $n$ натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

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

В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

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

Для каждого теста в отдельной строке вывести сумму $НОД$ всех возможных пар.

Тесты

№	Входные данные	Выходные данные
1	3 4 10 20 30 40 3 7 5 12 3 125 15 25	70 3 35
2	2 3 12 7 8 4 5 14 25 11	6 10
3	4 4 5 6 7 8 4 8 6 2 9 3 2 15 6 5 12 25 29 19 11	7 11 6 10

Код

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    int n, m, sum;
    cin >> n;
    while(n-- > 0) {
        cin >> m; 
        int ns[m];
        for(int i = 0; i < m; i++) cin >> ns[i];
        sum = 0;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);
        }
        cout << sum << endl;
    }
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a%b);

}

int main() {

int n, m, sum;

cin >> n;

while(n-- > 0) {

cin >> m;

int ns[m];

for(int i = 0; i < m; i++) cin >> ns[i];

sum = 0;

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

for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);

}

cout << sum << endl;

}

Решение

Алгоритм решения этой задачи очень простой: чтобы найти сумму НОД всех пар чисел в строке нужно сначала найти все сочетания по два числа из строки, потом посчитать НОД для каждой пары и сложить все НОД.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 2892. Сумма значений

24/06/2018 by Костя Григорян

Задача

Найдите сумму значений функции
$$f \left(x \right ) = x + \frac{1}{x}$$
в нескольких целых точках.

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

В первой строке задано количество точек $n$ $\left (1 \leqslant n \leqslant 50 \right ).$ В следующей строке заданы $n$ целых чисел $x_1, x_2, …, x_n$ — точки, значения функции в которых нужно просуммировать $\left (0 \leqslant \left |x_i \right | \leqslant 10^9 \right ).$

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

Выведите одно число — сумму значений функции $f \left(x \right )$ в заданных точках. Ответ считается правильным, если абсолютная или относительная погрешность не превышает $10^{-9}.$

Тесты

Входные данные	Выходные данные
$3$	$7.833333333333333$
$1 \ 2 \ 3$
$2$	$0$
$1 \ -1$
$5$	$4.265140415140415$
$10 \ -13 \ 21 \ -18 \ 4$
$1$	$10.1$
$10$

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

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

int main() {
    vector <long double> x;
    int n;
    long double ans=0;
    cin >> n;
    x.resize(n);
    for(int i=0; i<n; i++) 
    {
        cin >> x[i];
    }
    for(int i=0; i<n; i++)
    {
        ans+=x[i]+1.0/x[i];
    }
    cout.precision(15);
    cout << fixed << ans;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <long double> x;

int n;

long double ans=0;

cin >> n;

x.resize(n);

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

{

cin >> x[i];

}

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

{

ans+=x[i]+1.0/x[i];

}

cout.precision(15);

cout << fixed << ans;

return 0;

}

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

Мы просто суммируем значения функции в каждой точке. Тут использовали тип long double для точек и значений функции для меньшей погрешности.

Ссылки

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

Related Images:

e-olymp 9. N-значные числа

02/01/2018 by Андрей Лисовой

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]10[/latex] [latex]0[/latex]
[latex]2[/latex]	[latex]1[/latex] [latex]22[/latex]
[latex]4[/latex]	[latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex]	[latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex]	[latex]144[/latex] [latex]111111129[/latex]

Код программы (Цикл)

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

int Sum(int a) {
    int sum=0;
    while(a>0) {
        sum+=a%10;
        a/=10;
    }
    return sum;
}

int Mult(int a) {
    int mult=1;
    while(a>0) {
        mult*=a%10;
        a/=10;
    }
    return mult;
}

int main() {
    int n,ch=0,sum=0,mult=0,a;
    bool b=true;
    cin>>n;
    if(n==1) cout<<10<<" "<<0;
    else {
        if(n>1 and n<8) {
            for(int i=pow(10,n-1); i<pow(10,n); i++) {
                sum=Sum(i);
                mult=Mult(i);
                if((sum==mult) and b==true) {a=i;ch++;b=false;}
                else {
                    if(sum==mult) ch++;
                }
            }
            cout<<ch<<" "<<a;
        }
        else {
            if(n==8) cout<<224<<" "<<11111128;
            if(n==9) cout<<144<<" "<<111111129;
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int Sum(int a) {

int sum=0;

while(a>0) {

sum+=a%10;

a/=10;

}

return sum;

}

int Mult(int a) {

int mult=1;

while(a>0) {

mult*=a%10;

a/=10;

}

return mult;

}

int main() {

int n,ch=0,sum=0,mult=0,a;

bool b=true;

cin>>n;

if(n==1) cout<<10<<" "<<0;

else {

if(n>1 and n<8) {

for(int i=pow(10,n-1); i<pow(10,n); i++) {

sum=Sum(i);

mult=Mult(i);

if((sum==mult) and b==true) {a=i;ch++;b=false;}

else {

if(sum==mult) ch++;

}

cout<<ch<<" "<<a;

}

else {

if(n==8) cout<<224<<" "<<11111128;

if(n==9) cout<<144<<" "<<111111129;

}

return 0;

}

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

Код программы (Массив)

#include <iostream>
using namespace std;

int main() {
    int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
    int n;
    cin>>n;
    cout<<x[2*n-2]<<" "<<x[2*n-1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};

int n;

cin>>n;

cout<<x[2*n-2]<<" "<<x[2*n-1];

return 0;

}

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)

Related Images:

MLoop 10

08/11/2015 by Катя Писова

Вычислите с точностью [latex]\varepsilon[/latex] значение функции $f\left( x \right) = \text{ch}x$ . При вычислениях допустимо использовать только арифметические операции.

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

Для нахождения значения функции $f\left( x \right) = \text{ch}x$ (гиперболический косинус) с точностью [latex]\varepsilon[/latex] воспользуемся формулой Тейлора (разложение функции в бесконечную сумму степенных функций):[latex]chx=1+\frac{x^2}{2}+\frac{x^4}{4}+[/latex]…[latex]=\sum_{n=0}^{\infty}\frac{1}{(2n+1)!}\times x^{2n}[/latex]. [latex]x_n=\frac{1}{(2n+1)!}\times x^{2n}[/latex], тогда [latex]x_{n-1}=\frac{1}{(2(n-1)+1)!}\times x^{2(n-1)}[/latex]. Рекуррентное соотношение [latex]x_n[/latex] и [latex]x_{n-1}=[/latex][latex]\frac{x_n}{x_{n-1}}=\frac{x^2}{2n\times(2n-1)}[/latex].

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

#include <iostream>
#include <cmath>
using namespace std;
 
double ch(double x, double e)
{
	double result = 1;
	double member = 1;
	for (int i = 1; abs(member) >= e; i++)
	{
		member *= x * x;
		member /= 2*i * (2*i - 1);
		result += member;
	}
	return result;
}
 
int main() 
{ 
	double x, e;
	cin >> x >> e;
	cout << ch(x, e);
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double ch(double x, double e)

{

double result = 1;

double member = 1;

for (int i = 1; abs(member) >= e; i++)

{

member *= x * x;

member /= 2*i * (2*i - 1);

result += member;

}

return result;

}

int main()

{

double x, e;

cin >> x >> e;

cout << ch(x, e);

return 0;

}

Тесты:

Входные данные		Выходные данные
x	e	ch(x)
9	0.01	4051.54
16	0.0001	4.44306e+06
0.85	0.00001	1.38353
0.11	0.001	1.00606

Здесь можно посмотреть решение задачи на ideone.com

Related Images:

Mif 15

26/10/2015 by Женя Максимова

Задача. Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин в четырехмерном пространстве.

Тесты

(1)

№	[latex]A_0[/latex]	[latex]A_1 [/latex]	[latex]A_2[/latex]	[latex]A_3[/latex]	[latex]B_0[/latex]	[latex]B_1[/latex]	[latex]B_2[/latex]	[latex]B_3[/latex]
1	1	0	0	0	2	0	0	0
2	1	0	0	0	3	0	0	0
3	-1	1	0	6	-2	-1	1	6
4	1	1	1	1	2	2	2	2
5	1	1	1	2	8	5	7	10
6	1	1	0	0	1	0	1	1
7	3	4	7	8	9	5	6	2
8	1	2	2	3	1	4	8	9

(2)

№	[latex]C_0[/latex]	[latex]C_1[/latex]	[latex]C_2[/latex]	[latex]C_3[/latex]	[latex]D_0[/latex]	[latex]D_1[/latex]	[latex]D_2[/latex]	[latex]D_3[/latex]	[latex]r[/latex]
1	1	1	0	0	2	1	0	0	1.000000
2	2	4	0	0	2	4	3	0	4.000000
3	-1	-1	0	6	2	1	1	6	1.154701
4	-9	-9	-9	-9	-5	-5	-5	-5	12.000000
5	8	0	0	0	2	1	1	1	1.414214
6	2	3	2	0	1	4	9	1	3.000000
7	7	4	11	15	15	5	12	9	9.000000
8	5	7	2	23	4	8	8	21	13.000000

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

#include "stdio.h"
#include <cmath>

double dot(double * u, double * v);
double abs(double * u);
double min(double a, double b, double c, double d);
void prod(double k, double * u, double * v);
void diff(double * a, double * b, double * c);
void summ(double * a, double * b, double * c);
bool in(double s);
bool in(double s, double t);
double sd(double s, double t);
double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];
double u[4],v[4],w0[4];

double InterSegmentDistance4d()
//input: four 4d points P0, P1, Q0, Q1
// output: r = minimal distance between lines segments P0P1 and Q0Q1
    {
        double r = 0;
        //calculation of three vectors
        //u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0
        diff(P1, P0, u);  diff(Q1, Q0, v);  diff(Q0, P0, w0);
        //calculation of supporting scalar variables
        //a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v
        double  a, b, c, d, e;
        a = dot(u,u);  // a=u^2;
        b = dot(u,v);         
        c = dot(v,v);  // c=v^2;
        d = dot(u,w0);
        e = dot(v,w0);
        //calculation of main determinant
        // D = b^2 - a*c
        double D = b*b - a*c;
        if (D == 0) //lines are parallel
            {
                double t0=-e/c; 
                double t1=-e/c; 
                double s0 = (-e+b)/c ; 
                double s1= (e-c)*b/(c*a);
                if (in(t0) || in(t1) || in(s0) || in(s1))
                    {
                        double wq[4];
                        prod(e/c,v,  wq);  //projection w0 on line q
                        double wd[4];
                         diff(w0,wq,  wd);
                          r = abs(wd);
                           return r ; //r = |w0 - wq|
                    }
                //else minimal distance between segments equals minimal distance between ends of segments
                        r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));
                         return r;   
            }
        // else lines are not parallel
            {
                //calculation of determinants
                double D1 = b*e - c*d,  D2 = a*e - b*d;
                //calculation of parameters for minimal segment between lines
                double sc = D1/D, tc = D2/D;
                if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines
                    {
                        return r = sd(sc,tc); // r = |wc|
                    }
                //else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]
                    {
                        double t1 = 0,   s1=_(d/a);
                        double t2 = _(-2*e/c), s2=0;
                        double t3 = 1,   s3=_(2*(b+d)/a);
                        double t4 = _(2*(b+e)/c), s4=0;
                         return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4)); 
                    }
            }
    }

int main()
    {
        scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);
        scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);
        scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);
        scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);
         printf("%lf\n", InterSegmentDistance4d());
          return 0;
    }

double dot(double * u, double * v)//scalar production of two vectors
    {
        return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];
    }

double abs(double * u)//length of vector
    {
        return sqrt(dot(u,u));
    }

double min(double a, double b, double c, double d)//minimal from four values
    {
        double m = a;
        if(m>b) m = b;
         if(m>c) m = c;
          if(m>d) m = d;
           return m;
    }

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)
    {
        c[0]=a[0]-b[0];
        c[1]=a[1]-b[1];
        c[2]=a[2]-b[2];
        c[3]=a[3]-b[3];
    }

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)
    {
        c[0]=a[0]+b[0];
        c[1]=a[1]+b[1];
        c[2]=a[2]+b[2];
        c[3]=a[3]+b[3];
    }

void prod(double k, double * u, double * v)//production of number and vector
    {
        v[0] = k * u[0];
        v[1] = k * u[1];
        v[2] = k * u[2];
        v[3] = k * u[3];
    }

bool in(double s)//checking if the vatue is in [0,1]
    {
        return 0 <= s && s <= 1 ;
    }

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]
    {
        return  in(t) && in(s);
    }

double sd(double s, double t)//distance between two points defined by two parameters s and t
    {
        double Pc[4], Qc[4], W[4];
        prod(s,u, Pc);
        prod(t,v, Qc);
         summ(Pc,P0, Pc);
         summ(Qc,Q0, Qc);
          diff(Qc, Pc, W);
           return  abs(W);
    }

double _(double s)//restrict a value s on the interval [0,1]
    {
        double s1 = s;
        if(s > 1)s1 = 1;
        if(s < 0)s1 = 0;
         return s1;
    }

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

#include "stdio.h"

#include <cmath>

double dot(double * u, double * v);

double abs(double * u);

double min(double a, double b, double c, double d);

void prod(double k, double * u, double * v);

void diff(double * a, double * b, double * c);

void summ(double * a, double * b, double * c);

bool in(double s);

bool in(double s, double t);

double sd(double s, double t);

double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];

double u[4],v[4],w0[4];

double InterSegmentDistance4d()

//input: four 4d points P0, P1, Q0, Q1

// output: r = minimal distance between lines segments P0P1 and Q0Q1

{

double r = 0;

//calculation of three vectors

//u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0

diff(P1, P0, u); diff(Q1, Q0, v); diff(Q0, P0, w0);

//calculation of supporting scalar variables

//a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v

double a, b, c, d, e;

a = dot(u,u); // a=u^2;

b = dot(u,v);

c = dot(v,v); // c=v^2;

d = dot(u,w0);

e = dot(v,w0);

//calculation of main determinant

// D = b^2 - a*c

double D = b*b - a*c;

if (D == 0) //lines are parallel

{

double t0=-e/c;

double t1=-e/c;

double s0 = (-e+b)/c ;

double s1= (e-c)*b/(c*a);

if (in(t0) || in(t1) || in(s0) || in(s1))

{

double wq[4];

prod(e/c,v, wq); //projection w0 on line q

double wd[4];

diff(w0,wq, wd);

r = abs(wd);

return r ; //r = |w0 - wq|

}

//else minimal distance between segments equals minimal distance between ends of segments

r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));

return r;

}

// else lines are not parallel

{

//calculation of determinants

double D1 = b*e - c*d, D2 = a*e - b*d;

//calculation of parameters for minimal segment between lines

double sc = D1/D, tc = D2/D;

if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines

{

return r = sd(sc,tc); // r = |wc|

}

//else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]

{

double t1 = 0, s1=_(d/a);

double t2 = _(-2*e/c), s2=0;

double t3 = 1, s3=_(2*(b+d)/a);

double t4 = _(2*(b+e)/c), s4=0;

return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4));

}

int main()

{

scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);

scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);

scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);

scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);

printf("%lf\n", InterSegmentDistance4d());

return 0;

}

double dot(double * u, double * v)//scalar production of two vectors

{

return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];

}

double abs(double * u)//length of vector

{

return sqrt(dot(u,u));

}

double min(double a, double b, double c, double d)//minimal from four values

{

double m = a;

if(m>b) m = b;

if(m>c) m = c;

if(m>d) m = d;

return m;

}

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)

{

c[0]=a[0]-b[0];

c[1]=a[1]-b[1];

c[2]=a[2]-b[2];

c[3]=a[3]-b[3];

}

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)

{

c[0]=a[0]+b[0];

c[1]=a[1]+b[1];

c[2]=a[2]+b[2];

c[3]=a[3]+b[3];

}

void prod(double k, double * u, double * v)//production of number and vector

{

v[0] = k * u[0];

v[1] = k * u[1];

v[2] = k * u[2];

v[3] = k * u[3];

}

bool in(double s)//checking if the vatue is in [0,1]

{

return 0 <= s && s <= 1 ;

}

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]

{

return in(t) && in(s);

}

double sd(double s, double t)//distance between two points defined by two parameters s and t

{

double Pc[4], Qc[4], W[4];

prod(s,u, Pc);

prod(t,v, Qc);

summ(Pc,P0, Pc);

summ(Qc,Q0, Qc);

diff(Qc, Pc, W);

return abs(W);

}

double _(double s)//restrict a value s on the interval [0,1]

{

double s1 = s;

if(s > 1)s1 = 1;

if(s < 0)s1 = 0;

return s1;

}

Алгоритм и его обоснование

Расстояние между отрезками в четырехмерном пространстве находится по-разному, в зависимости от взаимного расположения этих отрезков. Тут мы можем выделить два основных случая:

Отрезки лежат на параллельных прямых или на одной прямой.
Отрезки лежат на пересекающихся либо на скрещивающихся прямых.

Чтобы выяснить, с каким случаем мы имеем дело, рассмотрим общую картину взаимного расположения отрезков и опишем ее математически:

По условию нам заданы 4 точки: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] — концы двух отрезков. Для удобства представления уравнений и точек, связанных с ними, обозначим их [latex]P_0[/latex], [latex]P_1[/latex], [latex]Q_0[/latex] и [latex]Q_1[/latex] соответственно. Через эти пары точек мы можем провести 2 прямые [latex]p[/latex] и [latex]q[/latex], параметрические уравнения которых имеют вид:

[latex]

\begin{matrix}
\vec p = P_0 + \vec u \cdot s \\
\vec q = Q_0 + \vec v \cdot t
\end{matrix}

[/latex],

где векторы:

[latex]

\begin{matrix}

\vec u = P_1 — P_0\\

\vec v = Q_1 — Q_0

\end{matrix}

[/latex],

а [latex]s[/latex] и [latex]t[/latex] — параметры. При [latex]s=0[/latex] или [latex] t=0[/latex] мы получаем начальную точку соответствующего отрезка, а при [latex]s=1[/latex] или [latex]t=1[/latex] — конечную. При произвольном значении параметра мы получаем произвольную точку на прямой.

Рассмотрим вектор [latex]\vec w = Q — P[/latex] , соединяющий 2 произвольные точки на этих прямых. Легко показать, что вектор [latex]\vec w[/latex] соединяет 2 ближайшие точки [latex]Q_c[/latex] и [latex]P_c[/latex] при условии:

[latex]\vec w \perp p[/latex] и [latex]\vec w \perp q[/latex].

Этому условию соответствует система из двух уравнений:

[latex] \begin{cases}
\vec u \cdot \vec w = 0\\
\vec v \cdot \vec w = 0
\end{cases}

[/latex]

Распишем ее для [latex]\vec w = Q_0 — P_0 + \vec v \cdot t — \vec u \cdot s = \vec w_0 + \vec v \cdot t — \vec u \cdot s[/latex] :
[latex]

\begin{cases}
\vec u \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0\\
\vec v \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0
\end{cases}

[/latex]

Введем вспомогательные скалярные переменные:
[latex]

\begin{matrix}

a&=&\vec u \cdot \vec u\\
b&=&\vec u \cdot \vec v\\
c&=&\vec v \cdot \vec v\\
d&=&\vec u \cdot \vec w_0\\
e&=&\vec v \cdot \vec w_0

\end{matrix}

[/latex]

Теперь наша система будет выглядеть так:

[latex]

\begin{cases}
d — a \cdot s + b \cdot t = 0 \\
e — b \cdot s + c \cdot t = 0
\end{cases}
[/latex]

Перепишем систему в удобном для нас виде:

[latex] \begin{cases}
a \cdot s — b \cdot t = d \\
b \cdot s — c \cdot t = e
\end{cases}
[/latex]

Решение этой системы мы можем получить, например, методом Крамера.

Главный определитель системы: [latex]D = b^2 — a \cdot c[/latex]

Два вспомогательных определителя:
[latex] \begin{matrix}
D_1 = b \cdot e — c \cdot d\\
D_2 = a \cdot e — b \cdot d\\
\end{matrix}
[/latex] Если [latex]D \neq 0[/latex], то существует единственное решение:

[latex]

\begin{cases}
s_c = \frac{D_1}{D} \\
t_c = \frac{D_2}{D}
\end{cases}
[/latex]

Если же мы получаем [latex]D = 0[/latex], легко показать, что отрезки параллельны. То есть мы имеем дело со случаем 1.

Тогда:

а) Если хотя бы одна точка одного отрезка проецируется на другой отрезок, то расстояние между отрезками равняется расстоянию между прямыми.

Найдем проекцию точки [latex]P_0[/latex] на линию [latex]q[/latex]. Для этого сначала найдем вектор, который является проекцией вектора [latex]\vec w_0[/latex] на линию [latex]q[/latex].

[latex]\vec w_q=(\vec w_0 \cdot \vec v) \cdot \frac{\vec v}{v^2}[/latex].
Конец полученного вектора находится в точке [latex]Q_0[/latex], а начало в новой точке [latex]P_{0q}=Q_0-\vec w_q[/latex]. Соединим точки [latex]P_0[/latex] и [latex]P_{0q}[/latex] вектором [latex]\vec w_p = P_{0q} — P_0[/latex]. Длина полученного вектора и будет искомым расстоянием: [latex]r = \left| P_0 P_{0q} \right|[/latex].

Для проверки условия а) необходимо получить проекции остальных исходных точек на отрезки:
[latex] \begin{matrix}
P_{1q} = P_{0q} + \vec u\\
Q_{0p} = P_0 + \vec w_q\\
Q_{1p} = Q_{0p} + \vec v
\end{matrix}
[/latex]

Если точка [latex]P_{0q}[/latex] лежит на прямой [latex]q[/latex], задаваемой уравнением:
[latex]\vec q = Q_0 + \vec v \cdot t[/latex],
то определить, принадлежит ли точка [latex]P_{0q}[/latex] отрезку [latex]Q_0 Q_1[/latex] можно, решив уравнение:
[latex]P_{0q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q + \vec v \cdot t[/latex].
Домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение: [latex] 0 = e + c \cdot t[/latex], отсюда [latex]t = \frac{-e}{c}[/latex].

Если [latex]t \in \left[0,1\right][/latex], то точка [latex]P_{0q}[/latex] лежит на отрезке [latex]Q_0 Q_1[/latex]. Если же нет, переходим к аналогичной проверке следующих точек:

[latex]P_{1q}:[/latex] [latex]P_{1q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q — \vec u + \vec v \cdot t[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение:

[latex] 0 = e — b + c \cdot t[/latex],
отсюда [latex]t = \frac{-e+b}{c}[/latex].
[latex]Q_{0p}:[/latex] [latex]Q_{0p} = P_0 + \vec u \cdot s[/latex].
[latex]0 =-\vec w_q + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} + a \cdot s[/latex],
отсюда [latex]s = \frac{e \cdot b}{c \cdot a}[/latex].
[latex]Q_{1p}:[/latex] [latex]Q_{1p} = P_0 + \vec u \cdot s[/latex].
[latex] 0 = -\vec w_q — \vec v + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} — b + a \cdot s[/latex],
отсюда [latex]s = \frac{(e — c) \cdot b}{c \cdot a}[/latex].
б) В противном случае, расстояние между отрезками равняется минимальному расстоянию между их концами. Здесь задача предельно упрощается. Мы находим длины отрезков, попарно соединяющих 4 исходные точки, и выбираем наименьший из них.

Если же исходные отрезки лежат на пересекающихся либо на скрещивающихся прямых, мы также рассматриваем 2 случая:

а) Оба конца кратчайшего отрезка, соединяющего прямые, лежат на соответствующих исходных отрезках:
[latex]P_c \in P_0 P_1[/latex] и [latex]Q_c \in Q_0 Q_1[/latex].

В этом случае пара параметров [latex](s_c, \; t_c)[/latex] принадлежит области: [latex](s,t):\left[0,1\right]\times \left[0,1\right].[/latex]

То есть, решение тривиально: ответом будет дина вектора [latex]\vec w_c[/latex]

б) Хотя бы один из концов кратчайшего отрезка, соединяющего прямые, не лежит на исходном отрезке, то есть:
[latex]P_c \not\in P_0 P_1[/latex] или [latex]Q_c \not\in Q_0 Q_1[/latex],
что соответствует значениям параметров [latex]s_c \not\in \left[0,1\right][/latex] или [latex]t_c \not\in \left[0,1\right][/latex].

В этом случае минимальное расстояние между отрезками определяется на границе области: [latex](s,t):\left[0,1\right]\times \left[0,1\right][/latex] (см. рисунок ниже):

Здесь решением является длина кратчайшего отрезка.

Длину отрезка, соединяющего 2 прямые, можно оценивать по квадрату длины вектора [latex]\vec v[/latex]: [latex]w^2=(\vec w)^2=(\vec w_0 — \vec u \cdot s + \vec v \cdot t)^2[/latex].

В частности, минимум [latex]w^2[/latex] достигается в точке [latex](s_c,t_c)[/latex].
Однако в случае б) мы должны найти минимум расстояния на границе нашей области, то есть решить задачу нахождения минимума при ограничениях (решить задачу условной минимизации). В нашем случае ограничения имеют очень простой вид — оси координат, и две линии, параллельные им. Поэтому мы можем решить на четырех границах 4 упрощенные задачи минимизации, а затем выбрать наименьшее решение.

Замечание: В пространстве параметров функция [latex]w^2(s,t)[/latex] представляет из себя эллиптический параболоид. Однако для простоты мы выше изобразили его линии уровня в виде окружностей. Типичный вид эллиптического параболоида и его линий уровня представлен на рисунках ниже:

Рассмотрим поочередно все 4 ограничения и решим задачу для них:

(1) Пусть [latex]t=t_1=0[/latex].

Тогда: [latex]{w^2\mid_{t_1=0}} = (\vec w_0-\vec u \cdot s_1)^2[/latex].

Для определения экстремума приравняем производную к нулю:[latex] \begin{array}{r}
\frac{d}{ds_1}{(\vec w_0-\vec u \cdot s_1)^2}=0\\
2 \cdot (\vec w_0-\vec u \cdot s_1) \cdot (- \vec u)=0\\
-d +a \cdot s_1=0\\
s_1=\frac{d}{a}
\end{array}
[/latex]

Легко показать, что при [latex]s_1>1[/latex] мы должны присвоить ему значение [latex]s_1=1[/latex], а если [latex]s<0[/latex] — значение [latex]s_1=0[/latex], так как мы не должны выходить за границы исходных отрезков.

Подставим полученное значение [latex]s[/latex] в уравнение прямой [latex]p[/latex] для точки [latex]P_c[/latex]:[latex]P_c = P_0 + \vec u \cdot s.[/latex]

А точка [latex]Q_c[/latex] совпадает с точкой [latex]Q_0[/latex]. Тогда первый минимум равен: [latex]r_1 = Q_0 P_c[/latex].

Аналогично найдем три остальных минимума [latex]r_2, r_3, r_4[/latex], приравняв [latex]s[/latex] к нулю, а затем [latex]t[/latex] и [latex]s[/latex] к единице. Наименьший из них и есть искомое расстояние [latex]r[/latex].

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

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. Векторы выбраны по причине ограниченности массива.