Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.
Входные данные
Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].
Выходные данные
Выведите последовательность чисел, упорядоченную согласно условию.
Тесты
№
Входные данные
Выходные данные
1
7
12 15 43 13 20 1 15
20 1 12 13 43 15 15
2
10
82 22 19 90 34 17 588 921 200 121
90 200 121 921 22 82 34 17 588 19
3
4
162 9801 37 14
9801 162 14 37
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
#include <algorithm>
usingnamespacestd;
boolcomp(constint&a,constint&b){
if(a%10==b%10)return(a<b);
elsereturna%10<b%10;
}
intmain(){
intn,a;
vector<int>array;
cin>>n;
for(inti=0;i<n;i++){
cin>>a;
array.push_back(a);
}
sort(array.begin(),array.end(),comp);
for(inta=0;a<n;a++){
cout<<array[a]<<" ";
}
return0;
}
Решение задачи
Для решения этой задачи необходимо объявить вектор, который будет хранить все числа, введенные пользователем, например,
array.
Сортировку будем проводить с помощью функции
sort. Для правильного упорядочивания чисел, напишем функцию компаратор
comp, для сравнения чисел и решения, стоит ли их менять местами.
В конце выводим вектор
array.
Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.
Входные данные
В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].
Выходные данные
Выведите элементы обновленного массива.
Тесты
№
Ввод
Вывод
1
7
6 -3 -7 4 -7 -4 5
-7 -7 6 -3 4 -4 5
2
2
100 -100
-100 100
3
6
-2 -2 7 3 99 -2
-2 -2 -2 7 3 99
4
5
1 1 1 1 1
1 1 1 1 1
Решение
Вместо обычных массивов будем использовать векторы, чтобы было удобнее добавлять элементы в конец. Минимальный элемент можно найти с помощью простого цикла: если какой-либо элемент вектора меньше
min, то
min присваивается значение этого элемента, и так пока не найдено наименьшее число. Подсчитаем, сколько раз оно встречается в векторе. Столько же раз его нужно добавить в новый вектор. Наконец, переносим в
v2 все оставшиеся элементы, не равные
min.
Игорю стало интересно какое количество перестановок букв его фамилии существует. Для этого он выписал на листке бумаге все буквы своей фамилии по алфавиту и начал создавать новые перестановки этих букву в лексикографическом порядке, записывая их на листок.
После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.
Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.
Подумав несколько ночей у него получилось написать программу которая находит слово анаграмму в словаре к другому — данному. Но перед ним встал новый вопрос, — а какое слово имеет наибольшее количество анаграмм в заданном словаре.
Его программа работала слишком долго, поэтому он попросил вас написать новую которая справилась бы с этой задачей.
Входные данные
Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.
Выходные данные
Вывести все слова что имеют максимальное количество анаграмм в нем.
Решение
Прочитаем словарь. Запишем в структуру
pair строку с исходным словом в
first и отсортированную в
second. Анаграммами будут являться слова с одинаковыми
second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по
second. Таким образом все слова анаграммы будут находиться рядом.
Теперь пройдемся по словарю и будем проверять соседние элементы. Если они равны, то мы будем увеличивать счетчик анаграмм, если же нет, то мы сравним максимальное количество анаграмм, найденное ранее, с текущим значением счетчика. Если они равны, то добавим индекс последнего слова анаграммы в массив индексов, если же больше, то мы очистим массив индексов и добавим туда индекс последнего слова анаграммы. В любом случае, при не равенстве соседних строк сбрасываем счетчик и продолжаем.
На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка
first.
Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]left langle 1,1 right rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.
Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]left langle 0,0 right rangle[/latex], а его дом расположен в точке [latex]left langle x_{h},y_{h} right rangle[/latex], и направление движения он менял [latex]k[/latex] раз.
Входные данные
В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0leq n,k,t,vleq 100)[/latex]
. Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5leq x_{h}, y_{h}leq 10^5)[/latex]
.
Выходные данные
Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.
Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]sumlimits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:
То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]sumlimits_{i=0}^k f(i, n)[/latex] — это вектор [latex]left langle a,b right rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]left langle a,b right rangle[/latex] и вектора [latex]left langle x_{h},y_{h} right rangle[/latex]:
$$sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$
И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]left langle 0,0 right rangle[/latex] и [latex]left langle 1,1 right rangle[/latex], то есть — [latex]sqrt{2}[/latex].
$$ sqrt{2} tv$$
Итого, выводим Good night Ia, если [latex]2t^2v^2 geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.
Вариант 2
Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = displaystylefrac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$
Для направления на северо-восток:
$$a_1 = 1, d = 4n Rightarrow S_{1}=frac{1 + 1 +4n(m_1-1)}{2}Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=1$ иначе, $m_1=displaystylefrac{k+1}{4}$
Для направления на юго-восток:
$$a_2 = 1+n, d = 4n Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=2$ иначе, $m_2=displaystylefrac{k+1}{4}$
Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=3$ иначе, $m_3=displaystylefrac{k+1}{4}$
Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=4$ иначе, $m_4=displaystylefrac{k+1}{4}$
Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push_front
Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
push_back
Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.
pop_back
Извлечь из дека последний элемент. Программа должна вывести его значение.
front
Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
back
Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
size
Вывести количество элементов в деке.
clear
Очистить дек (удалить из него все элементы) и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:
pop_front
pop_back
front
back
всегда корректны.
Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.
Тесты
№
Входные данные
Выходныеданные
1
push_back 3
push_back 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit
ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye
2
size
push_back 8
push_front 4
size
front
back
push_back 3
pop_front
front
pop_back
back
exit
0
ok
ok
2
4
8
ok
4
8
3
8
bye
Решение
Deque
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
#include <string>
usingnamespacestd;
structDeque
{
vector<int>box1;
vector<int>box2;
intn,box_size=0;
voidpush_front(intn)
{
box1.push_back(n);
box_size++;
}
voidpush_back(intn)
{
box2.push_back(n);
box_size++;
}
intpop_front()
{
if(box1.size()>0)
{
inta=box1[box1.size()-1];
box1.erase(box1.end()-1);
box_size--;
returna;
}
elseif(box2.size()>0)
{
inta=box2[0];
box2.erase(box2.begin());
box_size--;
returna;
}
return1;
}
intpop_back()
{
if(box2.size()>0)
{
inta=box2[box2.size()-1];
box2.erase(box2.end()-1);
box_size--;
returna;
}
elseif(box1.size()>0)
{
inta=box1[0];
box1.erase(box1.begin());
box_size--;
returna;
}
return1;
}
intfront()
{
if(box1.size()>0)
{
inta=box1[box1.size()-1];
returna;
}
elseif(box2.size()>0)
{
inta=box2[0];
returna;
}
return1;
}
intback()
{
if(box2.size()>0)
{
inta=box2[box2.size()-1];
returna;
}
elseif(box1.size()>0)
{
inta=box1[0];
returna;
}
return1;
}
intsize()
{
returnbox_size;
}
stringclear()
{
box1.erase(box1.begin(),box1.end());
box2.erase(box2.begin(),box2.end());
box_size=0;
return"ok";
}
stringexit()
{
return"bye";
}
};
intmain()
{
Dequea;
strings;
while(cin>>s)
{
if(s=="push_front")
{
intn;
cin>>n;
a.push_front(n);
cout<<"ok"<<endl;
}
if(s=="push_back")
{
intn;
cin>>n;
a.push_back(n);
cout<<"ok"<<endl;
}
if(s=="pop_front")
{
cout<<a.pop_front()<<endl;
}
if(s=="pop_back")
{
cout<<a.pop_back()<<endl;
}
if(s=="front")
{
cout<<a.front()<<endl;
}
if(s=="back")
{
cout<<a.back()<<endl;
}
if(s=="size")
{
cout<<a.size()<<endl;
}
if(s=="clear"){
a.clear();
cout<<a.clear()<<endl;
}
if(s=="exit")
{
cout<<a.exit()<<endl;
break;
}
}
return0;
}
Алгоритм решения
Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.
Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ 20 }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,20).
Обобщим задачу для последовательности длины [latex]n[/latex]
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).
Выходные данные:
[latex]n[/latex] чисел, [latex]i[/latex]-ое из которых является средним арифметическим всех членов последовательности, кроме [latex]i[/latex]-го ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).
Тесты
№
Входные данные
Выходные данные
1
4
The sequence must consist of at least two elements.
2
1 0 1
The arithmetic average of all elements of this series except the element №i is:
for i = 1: 0.5
for i = 2: 1
for i = 3: 0.5
3
10.1 2.4 11.3 0.8
The arithmetic average of all elements of this series except the element №i is:
for i = 1: 4.8(3)
for i = 2: 7.4
for i = 3: 4.4(3)
for i = 4: 7.9(3)
4
2.5 -1.5 4 -9 1.22
The arithmetic average of all elements of this series except the element №i is:
for i = 1: -1.32
for i = 2: -0.32
for i = 3: -1.695
for i = 4: 1.555
for i = 5: -1
Код на C++
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
usingnamespacestd;
intmain(){
vector<double>a,b;
doublecur,sum=0;
while(cin>>cur){
a.push_back(cur);
sum+=cur;
}
//Если последовательность состоит мене чем из двух элементов.
if(a.size()<2){
cout<<"The sequence must consist of at least two elements.";
}
else{
//Заполняем вектор b.
for(inti=0;i<a.size();++i){
b.push_back((sum-a[i])/(a.size()-1));
}
//Выводим ответ.
cout<<"The arithmetic average of all elements of this series except the element №i is:\n";
System.out.print("The arithmetic average of all elements of this series except the element №i is:\n");
for(inti=0;i<b.size();++i){
System.out.print("for i = "+(i+1)+": "+b.elementAt(i)+'\n');
}
}
}
}
Решение
Для начала, в первом цикле мы читаем числа из входного потока, помещаем их в вектор
a и прибавляем к переменной
sum, предназначенной для хранения суммы всех чисел последовательности. Последовательность должна состоять как минимум из двух элементов. Чтобы получить среднее арифметическое всех её членов, кроме [latex]i[/latex]-го, достаточно отнять [latex]i[/latex]-й элемент вектора
a от значения переменной
sum и разделить результат на количество членов такой неполной последовательности, а оно будет на единицу меньше размера вектора
a. Таким образом заполняется вектор
b, в котором хранятся элементы последовательности [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], после чего требуемая последовательность выводится.
Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, ….
Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.
Ввод
Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).
Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).
Вывод
Выведите первый момент времени, когда Рик и Морти закричат одновременно, или - 1, если они никогда не закричат одновременно.
Тесты
Ввод
Вывод
20 2
9 19
82
2 1
16 12
-1
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
usingnamespacestd;
intmain(){
inta,b,c,d,n,m;
vector<int>s;
cin>>a>>b;
cin>>c>>d;
for(inti=0;i<=100;i++)
{
for(intj=0;j<=100;j++)
{
n=b+i*a;
m=d+j*c;
if(m==n)
{
s.push_back(n);
}
}
}
if(s.empty()==true)
{
cout<<-1;
}elsecout<<s.at(0);
return0;
}
Решение
В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при a и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.
Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве
count. Останавливаем считывание, когда встречается
endl. После этого отсортировуем массив
count в порядке убывания частот.
После этого элементы массива
count, которые имеют ненулевую частоту, преобразовываем в элементы вектора
tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.
Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.
После этого, используя поиск в глубину, кодируем элементы массива
tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.
Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].
Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].
Выходные данные:
Некоторое количество натуральных чисел.
Тесты.
№
Входные данные
Выходные данные
[latex]a[/latex]
[latex]b[/latex]
[latex]p[/latex]
1
1
4
2, 3
2
0
1
Not found
3
5
5
5
4
6
20
7, 11, 13, 17, 19
Код программы (C++).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
usingnamespacestd;
intmain(){
cout<<"Primes: ";
boolprime;
inta,b;
cin>>a>>b;
vector<int>primes;
for(inte=2;e<=b;e++)
{
prime=true;
for(inti=0;i<primes.size();i++)
{
if((e%primes[i])==0)prime=false;
}
if(prime==true)
{
primes.push_back(e);
if(e>=a)cout<<e<<" ";
}
}
if(b<2)cout<<"Not found.";
return0;
}
Код программы (Java).
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
importjava.util.*;
importjava.math.*;
classsieveOfEratosthenes
{
publicvoidfind(inta,intb){
boolean[]prime=newboolean[b+1];
Arrays.fill(prime,Boolean.TRUE);
prime[0]=false;
prime[1]=false;
for(inti=2;i<=b;++i){
if(prime[i]){
for(intj=i*i;j<=b;j+=i){
prime[j]=false;
}
}
}
booleanprimes_found=false;//Попадает ли в промежуток хоть одно простое число?
for(inti=a;i<=b;++i){
if(prime[i]){
System.out.print(i+" ");
primes_found=true;
}
}
if(!primes_found)System.out.print("Not found");
}
}
classMain
{
publicstaticvoidmain(String[]args)
{
Scanner in=newScanner(System.in);
inta,b;
a=in.nextInt();
b=in.nextInt();
sieveOfEratosthenesc=newsieveOfEratosthenes();
c.find(a,b);
}
}
Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java. Условие задачи (с.135)
Задача. Найти объём параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z),[/latex] [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z).[/latex]
Найти угол в градусах, минутах и секундах между векторами [latex]\overrightarrow{a}=(a_x,a_y,a_z)[/latex] и [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex].
Входные данные:
Координаты векторов [latex] \overrightarrow{a}[/latex] и [latex]\overrightarrow{b}[/latex].
Выходные данные:
Угол в градусах, минутах и секундах.
Тесты
№
Входные данные
Выходные данные
1
1 1 4 20 31 12
53° 1′ 23″
2
1 61 12 1 11 1
7° 17′ 33″
3
1 0 0 0 0 1
90° 0′ 0″
4
-1 0 1 -2 2 1
44° 59′ 59″
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define _USE_MATH_DEFINES
#include
#include
usingnamespacestd;
intmain(){
doubleax,ay,az,bx,by,bz,mdla,mdlb,mdlab,ccos,ugl;
intgr=0,mn=0,sc=0;
cin>>ax>>ay>>az>>bx>>by>>bz;
mdla=sqrt(ax*ax+ay*ay+az*az);//формула длины вектора
mdlb=sqrt(bx*bx+by*by+bz*bz);
mdlab=mdla*mdlb;
ccos=(ax*bx+ay*by+az*bz)/mdlab;// формула косинус угла между векторами
ugl=acos(ccos)*180/M_PI;// получим угол по формуле перевода радиан в градусы
gr=ugl;// найдем градусы
ugl-=gr;
mn=ugl*60;// оставшаяся часть угла в минутах
ugl-=(double)mn/60;
sc=ugl*3600;// оставшаяся часть угла в секундах
cout<<gr<<"° "<<mn<<"' "<<sc<<"''";
return0;
}
Решение:
Для решения данной задачи необходимо найти косинус между векторами, а после перевести радианы в градусы.
Косинус между векторами найдем по формуле [latex] \cos \alpha = \frac{\vec{a}\vec{b}}{\left|\vec{a} \right|\left|\vec{b} \right|}[/latex] .
Скалярное произведение найдем по формуле [latex] \left|\vec{a} \right| \left|\vec{b} \right|={a}_{x}{b}_{x}+{a}_{y}{b}_{y}+{a}_{z}{b}_{z} [/latex] .
Модуль вектора найдем по формуле [latex] \left|\vec{a} \right| = \sqrt{ {{a}_{x}}^{2}+{{a}_{y}}^{2}+{{a}_{z}}^{2} } [/latex] ; [latex] \left|\vec{b} \right| = \sqrt{ {{b}_{x}}^{2}+{{b}_{y}}^{2}+{{b}_{z}}^{2} } [/latex] .
Затем переведем радианы в градусы по формуле [latex] \frac{180}{ \arccos (-1.0) \arccos (\cos \alpha )} [/latex] .
[latex] \arccos (-1.0) [/latex] это число [latex] \pi [/latex] .
Так как тетраэдр построен на векторах [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex], для данной задачи оптимальным решением будет использовать следующие формулы:
[latex]V = \frac {|\Delta|} {6}[/latex], где [latex]V[/latex] — объём тетраэдра, а [latex]\Delta[/latex] — определитель матрицы.
если значение определителя матрицы равно нулю, то либо некоторые из заданных векторов коллинеарны, либо нулевые, либо все они лежат в одной плоскости. Во всех этих случаях тетраэдр не может существовать, и программа выведет [latex]0[/latex];
если значение определителя не равно нулю, то программа вычислит объём тетраэдра. В случае, если определитель примет отрицательное значение, программа домножит значение объёма на [latex]-1[/latex], в результате чего оно станет положительным.
Задача. Найти площадь полной поверхности тетраэдра три стороны которого образованы векторами [latex]\overrightarrow{a}=(a_x,a_y,a_z)[/latex], [latex] \overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z)[/latex]. Тесты:
doubleA1A2=Math.sqrt(ax*ax+ay*ay+az*az);//вычислим длину ребра А1A2
doubleA1A3=Math.sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3
doublecosa=(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3
doublesina=Math.sqrt(1-cosa*cosa);//вычислим их синус
doubles1=0.5*A1A2*A1A3*sina;//найдём площадь поверхности
doubleA1A4=Math.sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4
doublecosb=(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4
doublesinb=Math.sqrt(1-cosb*cosb);//вычислим их синус
doubles2=0.5*A1A2*A1A4*sinb;//найдём площадь поверхности
doublecosc=(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4
doublesinc=Math.sqrt(1-cosc*cosc);//вычислим их синус
doubles3=0.5*A1A3*A1A4*sinc;//найдём площадь поверхности
doubleA2A3=Math.sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3
doubleA2A4=Math.sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4
doublecosd=((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4
doublesind=Math.sqrt(1-cosd*cosd);//вычислим их синус
doubles4=0.5*A2A3*A2A4*sind;//найдём площадь поверхности
doubles=s1+s2+s3+s4;//найдём площадь полной поверхности
System.out.println(s);//выведем её результат
}
}
Решение:
Координаты векторов находим по формуле:
[latex] \overrightarrow{A_2A_4}=(c_x-a_x,c_y-a_y,c_z-a_z) [/latex]
здесь [latex] a_x, a_y, a_z[/latex] — координаты точки [latex]A_2[/latex]; [latex]c_x, c_y, c_z[/latex] — координаты точки [latex]A_4[/latex];
Таким же образом находим остальные координаты векторов.
Модули векторов (длина ребер пирамиды)
Длина вектора [latex]\overrightarrow{a}(a_x;a_y;a_z)[/latex] выражается через его координаты формулой:
[latex] \left| \overrightarrow{A_1A_2} \right| =\sqrt { ({ a_x) }^{ 2 }+({ a_y) }^{ 2 }+({ a_z) }^{ 2 } } [/latex];
Таким же способом находим другие модули векторов.
Площадь грани можно найти по формуле:
[latex] s_1=\frac { 1 }{ 2 } \vec{A_1} \times \vec{A_2} \sin \angle{A_2A_3} [/latex]
где
[latex] \sin \angle{ A_2A_3 =\sqrt { 1-{ (\cos \angle{ A_2A_3) } }^{ 2 } } } [/latex]
Так же будем находить и другие.
Найдем угол между ребрами [latex] A_1A_2(a_x;a_y;a_z) [/latex] и [latex] A_1A_3(b_x;b_y;b_z) [/latex]:
[latex] \cos \angle{ A_2A_3 =\frac { a_x b_x+a_y b_y+a_z b_z }{ \left| A_2A_3 \right| } } [/latex]
Так мы найдём и другие 3 площади граней.
Площадь полной поверхности.
[latex] s=s_1+s_2+s_3+s_4. [/latex]
Угол между заданным вектором и [latex]Ox[/latex].
Угол между заданным вектором и [latex]Oy[/latex].
Угол между заданным вектором и [latex]Oz[/latex].
Тесты
Входные
данные
Выходные
данные
x
y
z
угол c Ox
угол c Oy
угол c Oz
0
0
1
90
90
0
0
9999.99
0
90
0
90
1
1
1
54.7456
54.7456
54.7456
-9999.5
-9999.5
-9999.5
-54.7456
-54.7456
-54.7456
0
0
0
невозможно при нулевом векторе
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include
#include
usingnamespacestd;
intmain(){
doublex,y,z,cosx,cosy,cosz;
cin>>x>>y>>z;//вводим координаты нашего вектора
if(x==0&&y==0&&z==0)//проверяем не является ли наш вектор нулевым
{
cout<<"Невозможно при нулевом векторе";//если у нас нулевой ветор выводить ошибку
}
else
{
cosx=x/(sqrt(x*x+y*y+z*z));//при ином условии подсчитываем косинусы углов между вектором и осями координат
cosy=y/(sqrt(x*x+y*y+z*z));
cosz=z/(sqrt(x*x+y*y+z*z));
cout<<acos(cosx)*180/M_PI<<" "<<acos(cosy)*180/M_PI<<" "<<acos(cosz)*180/M_PI;// выводим полученые углы координат в градусах
}
return0;
}
Решение задачи
Для начала проверим не является ли заданный вектор нулевым, так как он не будет образовывать угол между векторами. Если это нулевой, то выводить, что это невозможно при нулевом векторе. При другом условии решим задачу,а поскольку в условии нам даны координаты только 1 вектора, а для вычисления угла между 2 векторами нужно 2 пары координат, то будем считать, что [latex] Ox(1,0,0) [/latex], [latex] Oy(0,1,0) [/latex],[latex] Oz(0,0,1) [/latex].
Теперь мы можем вычислить угол между векторами через формулу[latex] \cos{ |\widehat { a,b } }|=\frac { \overrightarrow { a } \overrightarrow { b } }{ \left| \overrightarrow { a } \right| \left| \overrightarrow { b } \right| } [/latex], где [latex] \overrightarrow { a } \overrightarrow { b }=\ x_a\cdot{x_b}+y_a\cdot{y_b}+z_a\cdot{z_b}\[/latex] и [latex] { \left| \overrightarrow { a } \right| }=\sqrt{x_a^2+y_a^2+z_a^2} [/latex], которую можно сократить в соответствии с нашими значениями координат [latex]Ox,Oy,Oz [/latex] и в итоге получаем формулу [latex] \arccos=\frac{o}{\sqrt{x_a^2+y_a^2+z_a^2}} [/latex], где [latex] O [/latex] ось координат и [latex]o [/latex] значение по этой оси координат. В эту формулу поочередно подставляем наши значения и получаем косинусы углов между осями координат и заданным вектором. Для вычисления углов в радианах воспользуемся встроенной функцией [latex] acos [/latex], а для вычисления в градусах домножим полученный результат на 180 и разделим на встроенное значение числа [latex] \pi [/latex].
Задача.
Даны действительные числа [latex]a_{1},\ldots,a_{k}[/latex]. Получить [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}},[/latex] где [latex]\tilde{a}=\frac{1}{k}\sum\limits_{i=1}^{k}a_{i}.[/latex]
if(i==size_of_sum-1&&size%2!=0)sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size
elsesum.push_back(real[i]+real[size-i-1]);
}
sort(sum.begin(),sum.end(),f);// Сортировка по убыванию
cout<<sum[0];
return0;
}
Решение:
После считывания входного потока данных в вектор [latex]real[/latex] вещественных чисел, вычисляем размер вектора [latex]sum[/latex], равный половине количества элементов входного потока с округлением вверх. В случае нечетного количества элементов, последним элементом вектора [latex]sum[/latex] будет центральный элемент вектора [latex]real[/latex] увеличенный в два раза. Далее, после сортировки полученного вектора по убыванию, выводим первый элемент вектора.
Даны целые числа [latex] a_{1}\dots a_{n} [/latex]. Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением [latex] max(a_{1}\dots a_{n}) [/latex], домножить на [latex] max(a_{1}\dots a_{n}) [/latex].
Тестирование
№
Входные данные
Выходные данные
1.
1 2 3 4 3 2 1
1 8 3 4 3 2 1
2.
1 2 3 4 4 2 5 5 3 3 2 1
1 10 3 20 4 10 5 5 3 3 2 1
3.
11 4 6 7 9
11 4 6 7 9
4.
9 8 10 1 2 4 5 4 6 13
9 104 10 13 2 52 5 52 6 13
5.
-10 -4 -6 -7 -3 0 -1 -20
-10 0 -6 0 -3 0 -1 -20
Реализация
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include "iostream"
#include <vector>
usingnamespacestd;
intmain()
{
vector<int>a;
intn;
intmax_i=0;//номер максимального элемента
while(cin>>n)
a.push_back(n);
for(inti=0;i<a.size();i++)
{
if(a[i]>a[max_i])
max_i=i;
}
for(inti=0;i<max_i;i++)
{
if(i%2!=0)
a[i]*=a[max_i];
}
for(inti=0;i<a.size();i++)
cout<<a[i]<<" ";
return0;
}
Алгоритм решения
Считываем все целые числа до конца входного потока и записываем их в вектор [latex] a [/latex]. Затем:
Сравниваем между собой каждый элемент вектора, и если находится большее значение, то запоминается номер данного элемента.
Далее проходим все члены последовательности, предшествующие первому по порядку члену с максимальным значением.
Умножаем все элементы с четными номерами на [latex] max(a_{1}\dots a_{n}) [/latex].
Если в данной последовательности ни одно четное число не расположено после нечетного,
то получить все отрицательные члены последовательности, иначе –все положительные. Порядок следования чисел в обоих случаях заменяется на обратный.
Тесты
Входные данные
Выходные данные
-1 -4 5 7
7 5
1 2 3 4 5 -6
5 4 3 2 1
2 1 1 1 1
—
Алгоритм
Для начала считываем все числа входного потока и добавляем их в вектор.
Изначально предпологаем, что в полученной последовательности ни одно четное не расположено после нечетного (для этого заведем логический флаг, показывающий выполняется ли данное условие). Смотрим на пары последовательных элементов, пока не найдем противоречия условию или же не подтвердим его выполнение, дойдя до конца не изменив значение логического флага. Затем проходим исходную последовательность задом наперед и в зависимости от значения логического флага кладем в результирующую последовательность положительные или отрицательные члены исходной.
В итоге, получим требуемую в условии последовательность.
Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.
Решение
Для решения воспользуемся стандартным классом
vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией
min_element() или
max_element() (библиотека
algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.
Тесты
№
Входные данные
Выходные данные
1
-2 2 43 5 -10 12 0 -1
-3698 3698 79507 9245 -18490 22188 0 -1849
2
0 100 99 0 -1 1
0 100 99 0 -1 1
3
42 1 1 1 0 -1 24 -24 -42
74088 1764 1764 1764 0 -1764 42336 -42336 -74088
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
#include <algorithm>
usingnamespacestd;
intmain()
{
vector<int>x;
inta;
while(cin>>a)
x.push_back(a);
if(x.at(0)>=0)
{
intmin=*min_element(x.begin(),x.end());
for(int&i :x)
i*=min*min;
}
else
{
intmax=*max_element(x.begin(),x.end());
for(int&i :x)
i*=max*max;
}
for(inti:x)
cout<<i<<" ";
return0;
}
Замечание
Перед изменением значения членов последовательности и их выводом нам необходимо найти минимум или максимум, для чего необходимо знать значения всех её членов. В связи с этим, решить задачу в формате «считал — вывел» (потоковой обработкой) невозможно.
Считываем все числа из входного потока и записываем их в вектор исходной последовательности
sequence. Результатом работы нашей программы должна быть новая последовательность действительных чисел
result_sequence, которая задаётся по следующему правилу: первый член новой последовательности совпадает с первым членом исходной, второй член новой последовательности является последним членом исходной, третий – второй член исходной и так далее до исчерпания чисел. Иными словами, новая последовательность из [latex]2n[/latex] чисел на нечётных номерах имеет члены исходной последовательности (от первого и до [latex]n[/latex]-го включительно), чётным же номерам новой последовательности соответствуют члены исходной с номерами от [latex]n+1[/latex] до [latex]2n[/latex] включительно, записанные в обратном порядке.