Ещё 15 задач про числа за май 2018-го
Что ж, вот закончатся когда-нибудь мокрый снег и дождь, возможно, даже настанет лето, тогда и перестанем решать задачи. А пока что - очередная подборка алгоритмических задач на C++, предыдущая - в этой заметке.
Все задачи выполнялись как консольные приложения Visual Studio 2015, для быстрого поиска на странице статьи нужного слова в любом современном браузере можно использовать комбинацию клавиш Ctrl+F.
1. Серик и Берик собрали все яблоки в саду. Сезон подходит к концу и в саду осталось очень мало яблок. Вместе они собрали всего N корзинок с яблоками. По этой причине ребята решают поделить все собранные яблоки. Однако Серику не понравилось предложение Берика поделить всё количество яблок поровну. В этом случае кому-то может достаться больший вес яблок, так как у каждого яблока разный вес. Серик предложил поделить яблоки в каждой корзинке с помощью монетки.
Берик и Серик выложили яблоки из каждой корзинки перед собой в ряд. Таким образом, получилось N рядов с корзинками. Для каждого ряда ребята поочередно бросают монетку: если монетка падает решкой, то бросивший её берёт первое яблоко в ряду. Если выпадает орёл, то берут последнее яблоко в ряду.
Формат входных данных: первая строка содержит целое число N, количество корзинок с яблоками. Для каждой из N корзинок пишется две последующие строки: первая строка M – количество яблок в корзинке, вторая строка - веса Vi каждого яблока в корзинке.
Ограничения: 1 ≤ N ≤ 500 1 ≤ M ≤ 2000 0 ≤ Vi ≤ 999, 1 ≤ i ≤ M
Для каждой корзинки вывести, какой общий вес Берик и Серик получат из неё, при условии, что Серик бросает монетку первым.
//Visual Studio 2015
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
void error(char *message, int errorcode) { //Сообщение о статусе программы и выход
cout << endl << message;
cout << endl << "Press Enter to EXIT";
system("pause>nul");
exit(errorcode);
}
int main() {
ifstream f("input.txt");
if (!f) error("Can't open file data.txt", 1); //Не удалось открыть файл
int n;
f >> n;
if (f.fail() || n<2 || n>500) error("Bad N value!", 2); //Неверное N
vector < vector <int> > basket(n);
int summa = 0; //Всего яблок
for (int i = 0; i < n; i++) {
int m;
f >> m;
if (f.fail() || m<2 || m>2000) error("Bad M value!", 3); //Неверное M
for (int j=0; j<m; j++) {
double weight;
f >> weight;
if (f.fail() || weight<0 || weight>999) error("Bad weight value!", 4); //Неверный вес
basket[i].push_back (weight);
}
summa += m;
}
f.close();
srand(time(0));
vector <int> berik(n,0), serik(n,0);
int cnt = 0;
while (cnt < summa) { //пока всё не разобрали
for (int i = 0; i < n; i++) {
int m = basket[i].size();
if (m) {
//кинул Серик
int c = rand()%2;
int index = c ? 0 : m - 1;
serik[i] += basket[i][index];
cnt++;
basket[i].erase (basket[i].begin() + index);
m = basket[i].size();
if (m) {
//кинул Берик
int c = rand() % 2;
int index = c ? 0 : m - 1;
berik[i] += basket[i][index];
cnt++;
basket[i].erase(basket[i].begin() + index);
}
else {
//кинули Берика
}
}
}
}
for (int i = 0; i < n; i++) {
cout << "basket " << (i+1) << ", Berik = " << berik[i] << ", Serik = " << serik[i] << endl;
}
error("OK",0);
}
Файл input.txt был таким:
4 6 500 300 250 450 900 300 5 234 965 123 432 234 4 100 200 300 400 5 250 650 345 654 321
2. Создать массив целых чисел и заполнить его случайными значениями.
Размерность массива = 100 и диапазон значений чисел - от -100 до 100 включительно.
Найти непрерывный участок, на котором сумма положительных элементов максимальна.
При этом 0 считается положительным числом, а длина последовательности больше 1.
Если не использовать стандартных векторов и алгоритмов, то самое простое так:
//Visual Studio 2015
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
const int n = 100;
int a[n];
srand(time(0)); //чтобы числа были разными каждый раз!
for (int i=0; i<n; i++) {
a[i] = -100 + rand()%201;
cout << a[i] << " ";
}
int sum = 0; //текущая сумма чисел >=0
int maxsum = 0; //максимальная из таких сумм
int len = 0; //длина цепочки
int maxlen = 0; //максимальная из длин цепочек
int index = -1; //начало самой длинной цепочки
for (int i = 0; i < n; i++) {
if (a[i] >= 0) {
sum += a[i];
len++;
if (len > 1) {
if (sum > maxsum) {
index = i + 1 - len;
maxsum = sum;
maxlen = len;
}
}
}
else len = sum = 0;
}
if (index == -1) {
cout << "Chain not found!";
}
else {
cout << endl << "Length = " << maxlen << ", Summa = " << maxsum << ", Index = " << index;
cout << endl << "Items = ";
for (int i = index; i < index+ maxlen; i++) cout << a[i] << " ";
}
cin.get(); return 0;
}
3. Задана матрица А с 2 строками и 70 столбцами. 1-й элемент каждого столбца представляют собой абсциссу, а 2-й — ординату одной из 70 точек на плоскости. Определить среднее значение расстояний от начала координат тех точек, которые лежат в левой полуплоскости.
//Visual Studio 2015
#include <iostream>
#include <cmath>
using namespace std;
int main() {
const int n = 70;
double a[2][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < 2; i++) {
a[i][j] = -100 + rand()%201; //диапазон значений [-100;100]
}
cout << "Point " << (j+1) << "=(" << a[0][j] << "," << a[1][j] <<") ";
}
double average = 0;
int count = 0;
for (int j = 0; j < n; j++) {
if (a[0][j]<0) { //x<0, левая полуплоскость
average += sqrt(pow(a[0][j],2)+pow(a[1][j],2)); //прибавить очередное расстояние
count++;
}
}
if (count > 0 ) {
average /= count; //найти среднее
cout << endl << "Average = " << average;
}
else cout << endl << "Not found!";
cin.get(); return 0;
}
4. Задача о раскраске графа. Граф представлен структурой Вирта. Вот 3 работающих в консоли Visual Studio 2015 программки, не очень оптимизированы, зато с комментариями.
4.1. Обход в глубину
//Visual Studio 2015
//Последовательная раскраска вершин графа при помощи
//обхода графа в глубину.
//Граф представлен структурой Вирта.
#include <iostream>
#include <windows.h>
using namespace std;
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef struct L *Lref; // Тип: указатель на заголовочный узел.
typedef struct T *Tref; // Тип: указатель на дуговой узел.
//Описание типа заголовочного узла.
typedef struct L
{
int Key; //Имя заголовочного узла.
int Color; //Цвет раскраски.
int Count; //Количество предшественников.
Boolean Flag; //Флаг посещения узла при обходе.
Tref Trail; //Указатель на список смежности.
Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
};
//Описание типа дугового узла.
typedef struct T
{
Lref Id;
Tref Next;
};
class Spisok
{
private:
Lref Head; //Указатель на голову списка заголовочных узлов.
Lref Tail; //Указатель на фиктивный элемент
// в конце списка заголовочных узлов.
int MSet[256]; //Вспомогательное множество, содер-
//жащее 0,1,2...,n.
void SearchGraph(int, Lref *);
public:
Spisok() {//Инициализация списка заголовочных узлов.
Head = Tail = new (L);
}
Lref GetHead() { return Head; }
Lref GetTail() { return Tail; }
void MakeGraph();
void PrintGraph();
void Color(Lref, int);
void Postr(int);
};
void Spisok::Postr(int n)
//Построение вспомогательного множества MSet.
{
for (int i = 0; i<256; i++)
MSet[i] = (i <= n) ? 1 : 0;
}
void Spisok::SearchGraph(int w, Lref *h)
//Функция возвращает указатель на заголовочный узел
//с ключом w в графе, заданном структурой Вирта с указателем Head.
{
*h = Head; (*Tail).Key = w;
while ((**h).Key != w) *h = (**h).Next;
if (*h == Tail)
//В списке заголовочных узлов нет узла с ключом w.
//Поместим его в конец списка Head.
{
Tail = new (L); (**h).Count = 0;
(**h).Trail = NULL; (**h).Next = Tail;
}
}
void Spisok::MakeGraph()
//Функция возвращает указатель Head на структуру
//Вирта, соответствующую ориентированному графу.
{
int x, y;
Lref p, q; //Рабочие указатели.
Tref t, r; //Рабочие указатели.
Boolean Res; //Флаг наличия дуги.
cout << "Вводите начальную вершину дуги: ";
cin >> x;
while (x != 0)
{
cout << "Вводите конечную вершину дуги: "; cin >> y;
//Определим, существует ли в графе дуга (x,y)?
SearchGraph(x, &p); SearchGraph(y, &q);
r = (*p).Trail; Res = FALSE;
while ((r != NULL) && (!Res))
if ((*r).Id == q) Res = TRUE;
else r = (*r).Next;
if (!Res) //Если дуга отсутствует, то поместим её в граф.
{
t = new (T); (*t).Id = q;
(*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++;
}
cout << "Вводите начальную вершину дуги (0 - выход): "; cin >> x;
}
}
void Spisok::PrintGraph()
//Вывод структуры Вирта, заданной указателем
//Head и соответствующей ориентированному графу.
{
Lref p; //Рабочий указатель.
Tref q; //Рабочий указатель.
p = Head;
while (p != Tail)
{
cout << (*p).Key << "("; q = (*p).Trail;
while (q != NULL)
{
cout << (*(*q).Id).Key; q = (*q).Next;
}
cout << ")"; p = (*p).Next; cout << " ";
}
}
void Spisok::Color(Lref r, int n)
//Последовательная раскраска графа при помощи
//рекурсивного обхода графа в глубину.
//r - указатель на структуру Вирта.
//MSet - глобальное множество.
//n - количество вершин в графе.
{
Tref t, t1;
int i; //Параметр цикла.
Boolean Fl;
t = r->Trail; r->Flag = FALSE;
//Сейчас мы находимся в вершине r->Key.
//Исключим цвета всех вершин, смежных вершине
//r->Key, из множества MSet.
t1 = t;
while (t1 != NULL)
{
MSet[t1->Id->Color] = 0; t1 = t1->Next;
}
//Выбор цвета вершины: это "первый" элемент множества MSet.
Fl = TRUE; i = 1;
while (Fl)
if (MSet[i]) Fl = FALSE; else i++;
r->Color = i; //Цвет присвоен!
cout << "(" << r->Key << "," << r->Color << ") ";
//Восстановление вспомогательного множества MSet.
for (i = 0; i<256; MSet[i++] = 0);
for (i = 0; i <= n; MSet[i++] = 1);
// -------------
while (t != NULL)
{
if (t->Id->Flag) Color(t->Id, n);
t = t->Next;
}
}
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
//Если нет русских букв при вводе, поставьте шрифт Lucida Console в свойствах окна консоли
Spisok A;
Lref t; //Рабочий указатель для перемещения
// по списку заголовочных звеньев.
int n = 0; //Количество вершин в графе.
//Построение графа и вывод его структуры Вирта.
A.MakeGraph();
A.PrintGraph(); cout << endl;
//Раскраска с помощью рекурсивного обхода графа в глубину.
//Инициализация.
t = A.GetHead(); //Установлен рабочий указатель.
while (t != A.GetTail())
{
t->Flag = TRUE; t->Color = 0;
n++; t = (*t).Next;
}
// ------------------------------------
//Построение вспомогательного множества MSet.
A.Postr(n);
cout << "Результат раскраски: ";
A.Color(A.GetHead(), n);
system("pause");
return 0;
}
4.2. Обход в ширину
//Visual Studio 2015
// Последовательная раскраска графа при помощи
//обхода графа в ширину.
//Граф представлен структурой Вирта.
#include <iostream>
#include <windows.h>
using namespace std;
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef struct Leader *Lref; // Тип: указатель на заголовочный узел.
typedef struct Trailer *Tref; // Тип: указатель на дуговой узел.
//Описание типа заголовочного узла.
typedef struct Leader
{
int Key; //Имя заголовочного узла.
int Count; //Количество предшественников.
int Color; //Цвет раскраски.
Boolean Flag; //Флаг посещения узла при обходе.
Tref Trail; //Указатель на список смежности.
Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
};
//Описание типа дугового узла.
typedef struct Trailer
{
Lref Id;
Tref Next;
};
//Описание типа узла очереди.
typedef Lref TipElement; //Указатель на звено заголовочного списка.
typedef struct Zveno *svqz;
typedef struct Zveno
{
TipElement Element; //Указатель на список смежности.
svqz Sled;
};
class Spisok
{
private:
Lref Head; //Указатель на голову списка заголовочных узлов.
Lref Tail; //Указатель на фиктивный элемент
// в конце списка заголовочных узлов.
int MSet[256]; //Вспомогательное множество, содер-
//жащее 0,1,2...,n.
void Udalenie_A(svqz *, svqz *, TipElement *);
void Dobavlenie(svqz *, svqz *, TipElement);
void SearchGraph(int, Lref *);
public:
Spisok() {//Инициализация списка заголовочных узлов.
Head = Tail = new (Leader);
}
Lref GetHead() { return Head; }
Lref GetTail() { return Tail; }
void MakeGraph();
void PrintGraph();
void Color(Lref, int);
void Postr(int);
};
void Spisok::Postr(int n)
//Построение вспомогательного множества MSet.
{
for (int i = 0; i<256; i++)
MSet[i] = (i <= n) ? 1 : 0;
}
void Spisok::SearchGraph(int w, Lref *h)
//Функция возвращает указатель на заголовочный узел
//с ключом w в графе, заданном структурой Вирта с указателем Head.
{
*h = Head; (*Tail).Key = w;
while ((**h).Key != w) *h = (**h).Next;
if (*h == Tail)
//В списке заголовочных узлов нет узла с ключом w.
//Поместим его в конец списка Head.
{
Tail = new (Leader); (**h).Count = 0;
(**h).Trail = NULL; (**h).Next = Tail;
}
}
void Spisok::MakeGraph()
//Функция возвращает указатель Head на структуру
//Вирта, соответствующую ориентированному графу.
{
int x, y;
Lref p, q; //Рабочие указатели.
Tref t, r; //Рабочие указатели.
Boolean Res; //Флаг наличия дуги.
cout << "Вводите начальную вершину дуги: ";
cin >> x;
while (x != 0)
{
cout << "Вводите конечную вершину дуги: "; cin >> y;
//Определим, существует ли в графе дуга (x,y)?
SearchGraph(x, &p); SearchGraph(y, &q);
r = (*p).Trail; Res = FALSE;
while ((r != NULL) && (!Res))
if ((*r).Id == q) Res = TRUE;
else r = (*r).Next;
if (!Res) //Если дуга отсутствует, то поместим её в граф.
{
t = new (Trailer); (*t).Id = q;
(*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++;
}
cout << "Вводите начальную вершину дуги: "; cin >> x;
}
}
void Spisok::PrintGraph()
//Вывод структуры Вирта, заданной указателем
//Head и соответствующей ориентированному графу.
{
Lref p; //Рабочий указатель.
Tref q; //Рабочий указатель.
p = Head;
while (p != Tail)
{
cout << (*p).Key << "("; q = (*p).Trail;
while (q != NULL)
{
cout << (*(*q).Id).Key; q = (*q).Next;
}
cout << ")"; p = (*p).Next; cout << " ";
}
}
void Spisok::Dobavlenie(svqz *L, svqz *R, TipElement elem)
//Добавление элемента elem в очередь, заданную указателями L и R.
{
svqz K = new (Zveno);
K->Element = elem; K->Sled = NULL;
if (*L == NULL)
{
(*L) = K; (*R) = K;
}
else { (*R)->Sled = K; (*R) = K; }
}
void Spisok::Udalenie_A(svqz *L, svqz *R, TipElement *A)
//Удаление элемента из очереди, заданной указателями L и R и
//помещение удаленного элемента в переменную A.
{
svqz q;
if ((*L) != NULL)
if ((*L)->Sled != NULL)
{
(*A) = (*L)->Element; q = (*L);
(*L) = (*L)->Sled; delete q;
}
else {
(*A) = (*L)->Element; delete *L;
(*L) = (*R) = NULL;
}
}
void Spisok::Color(Lref H, int n)
//Последовательная раскраска графа при помощи обхода графа
//в ширину, начиная с вершины, заданной указателем H
//(нерекурсивный обход).
{
svqz L; // Указатель на начало очереди.
svqz R; // Указатель на конец очереди.
Lref p; // Рабочий указатель.
Tref t; // Рабочий указатель.
Tref t1;
int i; // Параметр цикла.
Boolean Fl;
L = R = NULL; // Создание пустой очереди.
Dobavlenie(&L, &R, H); H->Flag = FALSE;
while (L != NULL)
{ //Пока очередь не пуста...
Udalenie_A(&L, &R, &p);
t = p->Trail;
//Сейчас мы находимся в вершине r->Key.
//Исключим цвета всех вершин, смежных вершине
//r->Key, из множества MSet.
t1 = t;
while (t1 != NULL)
{
MSet[t1->Id->Color] = 0; t1 = t1->Next;
}
//Выбор цвета вершины - "первого" элемента множества MSet.
Fl = TRUE; i = 1;
while (Fl)
if (MSet[i]) Fl = FALSE; else i++;
p->Color = i; //Цвет присвоен!
cout << "(" << p->Key << "," << p->Color << ") ";
//Восстановление вспомогательного множества MSet.
for (i = 0; i<256; MSet[i++] = 0);
for (i = 0; i <= n; MSet[i++] = 1);
while (t != NULL)
{
if (t->Id->Flag)
{
Dobavlenie(&L, &R, t->Id);
t->Id->Flag = FALSE;
}
t = t->Next;
}
}
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
//Если нет русских букв при вводе, поставьте шрифт Lucida Console в свойствах окна консоли
Spisok A;
Lref t; //Рабочий указатель для перемещения
// по списку заголовочных звеньев.
int n = 0; //Количество вершин в графе.
//Построение графа и вывод его структуры Вирта.
A.MakeGraph();
A.PrintGraph(); cout << endl;
//Раскраска с помощью рекурсивного обхода графа в ширину.
//Инициализация.
t = A.GetHead(); //Установлен рабочий указатель.
while (t != A.GetTail())
{
t->Flag = TRUE; t->Color = 0;
n++; t = (*t).Next;
}
// ------------------------------------
//Построение вспомогательного множества MSet.
A.Postr(n);
cout << "Результат раскраски: ";
A.Color(A.GetHead(), n);
system("pause");
return 0;
}
4.3. Раскраска, если граф представлен списками смежности
//Visual Studio 2015
//Последовательная раскраска графа, представленного с помощью
//модифицированных списков смежности.
#include <iostream>
#include <windows.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define XRY 8 //Количество вершин графа.
typedef int Boolean;
typedef struct zveno *svqz;
typedef struct zveno
{
int Key; // Вершина графа.
svqz Up; // Указатель на смежную вершину.
svqz Sled;// Указатель на следующую смежную вершину.
};
class Spisok
{
private:
svqz Beg[XRY + 1]; //Массив указателей на вершины.
void Add_Ver(int);
int Find(int, int, svqz *);
void Add_duga(int, int);
void Make(int, int);
void Delinenok(int, int);
void Del_Duga(int, int);
void Del_Ver(int);
int Find_Color(int, int, svqz *);
public:
Spisok();
void Init_Graph();
void Make_Graph();
void Print_Graph();
void Color();
void Print_Color();
};
Spisok::Spisok()
{
for (int i = 0; i <= XRY; Beg[i++] = NULL);
}
void Spisok::Add_Ver(int x)
//Функция создания вершины x.
{
svqz Ukaz = new (zveno);
Ukaz->Sled = NULL;
Beg[x] = Ukaz;
}
void Spisok::Init_Graph()
//Функция инициализации модифицированных списков смежности.
{
for (int i = 1; i <= XRY; i++) Add_Ver(i);
}
int Spisok::Find(int x, int y, svqz *UkZv)
//Функция проверки смежности вершин y и x. Функция возвращает
//TRUE, если вершина x смежна с вершиной y. Указатель *UkZv,
//возвращает указатель на место y в списке смежности x. Если
//вершина x не смежна с вершиной y, то UkZv есть NULL.
{
svqz Ukaz;
Ukaz = Beg[x]->Sled;
while (Ukaz != NULL && Ukaz->Key != y)
Ukaz = Ukaz->Sled;
*UkZv = Ukaz;
return (Ukaz != NULL);
}
void Spisok::Add_duga(int x, int y)
//Функция создания дуги (x,y).
{
svqz Ukaz = new (zveno);
Ukaz->Sled = Beg[x]->Sled; Ukaz->Key = y;
Beg[x]->Sled = Ukaz;
}
void Spisok::Make(int x, int y)
//Функция создания ребра {x,y}.
{
svqz Ukaz;
if (!Find(x, y, &Ukaz))
{
Add_duga(x, y);
if (x != y) Add_duga(y, x);
Beg[x]->Sled->Up = Beg[y];
Beg[y]->Sled->Up = Beg[x];
}
}
void Spisok::Make_Graph()
//Функция построения модифицированных списков смежности.
{
int f;
for (int i = 1; i <= XRY; i++)
{
cout << "Введите вершины, смежные с " << i << "-й вершиной: ";
cin >> f;
while (f != 0)
{
Make(i, f);
cout << " ";
cin >> f;
}
cout << endl;
}
}
void Spisok::Delinenok(int x, int y)
//Функция удаления дуги (x,y).
{
svqz Ukaz;
svqz Ukazlenok;
Ukazlenok = Beg[x]; Ukaz = Beg[x]->Sled;
while (Ukaz != NULL && Ukaz->Key != y)
{
Ukazlenok = Ukaz; Ukaz = Ukaz->Sled;
}
if (Ukaz != NULL)
{
Ukazlenok->Sled = Ukaz->Sled;
delete Ukaz;
}
}
void Spisok::Del_Duga(int x, int y)
//Функция удаления ребра {x,y}.
{
Delinenok(x, y); Delinenok(y, x);
}
void Spisok::Del_Ver(int x)
//Функция удаления вершины x.
{
svqz Ukaz;
svqz Ukazlenok;
for (int i = 1; i <= XRY; i++) Delinenok(i, x);
Ukaz = Beg[x]; Beg[x] = NULL;
while (Ukaz != NULL)
{
Ukazlenok = Ukaz->Sled;
delete Ukaz; Ukaz = Ukazlenok;
}
}
void Spisok::Print_Graph()
//Функция вывода содеpжимого модифицированных
//списков смежности.
{
svqz UkZv;
for (int i = 1; i <= XRY; i++)
{
if (Beg[i] != NULL)
{
UkZv = Beg[i]->Sled;
cout << i << " - ";
while (UkZv != NULL)
{
cout << " " << UkZv->Key;
UkZv = UkZv->Sled;
}
}
cout << endl;
}
}
int Spisok::Find_Color(int x, int c, svqz *UkZv)
//Функция выявления возможности раскраски вершины x цветом c.
//Функция возвращает TRUE, если вершину x можно раскрасить.
//Указатель *UkZv, возвращает указатель на вершину, смежную с x
//и раскрашенную цветом c. Если вершину x можно раскрасить, то
//*UkZv есть NULL.
{
int i = 1;
while (!(Find(x, i, &(*UkZv)) &&
Beg[i]->Key == c) &&
i != x) i++;
return (i == x);
}
void Spisok::Color()
//Функция последовательной раскраски графа, заданного
//модифицированными списками смежности Beg.
{
int i = 1;
int c = 1;
svqz UkZv;
while (Beg[i] == NULL && i <= XRY) i++;
if (i != XRY)
{
Beg[i]->Key = c;
i++;
while (i <= XRY)
if (Beg[i] != NULL)
{
c = 1;
while (!Find_Color(i, c, &UkZv)) c++;
Beg[i]->Key = c; i++;
}
else i++;
}
else cout << "Граф отсутствует!";
}
void Spisok::Print_Color()
//Функция вывода раскраски графа, заданного
//модифицированными списками смежности Beg.
{
for (int i = 1; i <= XRY; i++)
if (Beg[i] != NULL)
cout << " Color " << i << " - " << Beg[i]->Key << endl;
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
//Если нет русских букв при вводе, поставьте шрифт Lucida Console в свойствах окна консоли
Spisok A;
//Инициализация графа.
A.Init_Graph();
//Построение графа.
A.Make_Graph();
//Вывод графа.
A.Print_Graph();
//Последовательная раскраска графа, представленного
//модифицированными списками смежности.
A.Color();
A.Print_Color();
system("pause");
return 0;
}
5. Даны целые положительные числа M, N и набор из M целых значений. Сформировать матрицу размера M х N, у которой в каждом столбце содержатся все числа из исходного набора, записанные в том же порядке.
//Visual Studio 2015
#include <iostream>
using namespace std;
int main() {
const int m = 5, n = 6; //размерности
int v[m] = {1,2,3,4,5}; //набор
int **a; //матрица
a = new int * [m];
for (int i = 0; i<m; i++) {
a[i] = new int[n];
for (int j = 0; j<n; j++) {
a[i][j] = v[i];
cout << a[i][j] << " ";
}
cout << endl;
}
cin.get();
return 0;
}
6. Вычислить сумму n первых членов ряда
интересный ряд
Как обычно, стараемся обойтись без лишних повторяющихся расчётов, накапливая части формулы в промежуточных переменных.
//Visual Studio 2015
#include <iostream>
using namespace std;
int main() {
int n = 10; //или ввести число
double x = 0.1; //x тоже должно быть задано
double sum = 0, z = 1, pr = 1;
for (int i=1; i<=2*n-1; i+=2) {
sum += z * pr * x / i;
x *= x*x;
pr *= (double)i / (i + 1);
z = -z;
}
cout.precision(15);
cout << sum;
cin.get();
return 0;
}
7. Два двузначных числа, записанных одно за другим , образуют четырёхзначное число, которое без остатка делится на их произведение. Найти все пары таких чисел.
//Visual Studio 2015
#include <iostream>
using namespace std;
int main() {
for (int a = 10; a < 100; a++) {
for (int b = 10; b < 100; b++) {
int c = a*100+b;
if (c%(a*b)==0) cout << endl << a << " " << b << " " << c << " " << a*b << " " << c/(a*b);
}
}
cin.get();
return 0;
}
8. Написать функцию для возведения целого значения x в натуральную степень y с временной сложностью алгоритма O(Log y)
//Visual Studio 2015
#include <iostream>
using namespace std;
int power(int x, unsigned int y) {
int res = 1;
while (y > 0) {
if (y & 1) res = res * x;
y = y >> 1; // y/=2;
x = x * x;
}
return res;
}
int main() {
cout << power(3,5);
cin.get();
return 0;
}
9. Представить заданную дробь в виде Египетской дроби.
Алгоритм не самый сильный и может переполнить стек для некоторых дробей.
//Visual Studio 2015
#include <iostream>
#include <string>
using namespace std;
string printEgyptian (int ch, int zn) {
if (ch == 0 || zn == 0) return "";
if (zn%ch == 0) return string("1/") + to_string(zn/ch);
if (ch%zn == 0) return to_string(ch) + string("/") + to_string(zn);
if (ch > zn) return to_string(ch) + string("/") + to_string(zn) +
string("+") + printEgyptian(ch%zn, zn);
int n = zn / ch + 1;
return string("1/") + to_string(n) +
string("+") + printEgyptian(ch*n - zn, zn*n);
}
int main() {
int ch = 7, zn = 15;
cout << ch << "/" << zn << "=" << printEgyptian(ch, zn);
cin.get();
return 0;
}
10. Найти угол между часовой и минутной стрелками на 12-часовом циферблате.
Вот здесь мы искали время до момента, когда стрелки окажутся на одной линии, попробуем просто определить угол между стрелками.
Угол считается "без знака" и принимает значения от 0 до 180 градусов.
//Visual Studio 2015
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int calcAngle(double h, double m) {
if (h <0 || m < 0 || h >12 || m > 60) return INT_MAX;
if (h == 12) h = 0;
if (m == 60) m = 0;
int hour_angle = 0.5 * (h * 60 + m);
int minute_angle = 6 * m;
int angle = abs(hour_angle - minute_angle);
return min(360 - angle, angle);
}
int main() {
cout << "For time 9:60=" << calcAngle(9, 60) << endl;
cout << "For time 11:36=" << calcAngle(11, 36) << endl;
cout << "For time 6:01=" << calcAngle(6, 1) << endl;
cin.get();
return 0;
}
Или ещё проще:
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
double calcAngle(unsigned h, unsigned m) {
h += m / 60;
h %= 12;
m %= 60;
double hour_angle = 0.5 * (h * 60 + m);
double minute_angle = 6 * m;
double angle = abs(hour_angle - minute_angle);
angle = min (360 - angle, angle);
return angle;
}
int main() {
cout << calcAngle(9,120); //30
cout << endl << calcAngle(15, 30); //75
cin.get();
return 0;
}
11. Найти n-ое по порядку число Каталана.
Используем подход без рекурсии на основе вычисления биномиальных коэффициентов, его временная сложность будет порядка O(n). Нумерация чисел, по определению, предполагается с нуля.
//Visual Studio 2015
#include <iostream>
using namespace std;
unsigned long int binomialCoeff (unsigned int n, unsigned int k) {
unsigned long int res = 1;
if (k > n - k) k = n - k; // C(n, k) = C(n, n-k)
for (int i = 0; i < k; ++i) { // [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
res *= (n - i);
res /= (i + 1);
}
return res;
}
unsigned long int catalan(unsigned int n) {
unsigned long int c = binomialCoeff(2 * n, n);
return c / (n + 1);
}
int main() {
cout << catalan(10);
cin.get();
return 0;
}
12. Русское крестьянское умножение :)
Так у них, но не у нас, называют народный метод умножения, основанный на умножении и делении на два.
//Visual Studio 2015
#include <iostream>
using namespace std;
unsigned int russianPeasantMult (unsigned int a, unsigned int b) {
int res = 0;
while (b > 0) {
if (b & 1) res = res + a;
a = a << 1;
b = b >> 1;
}
return res;
}
int main() {
cout << "30*12=" << russianPeasantMult(30,12) << endl;
cout << "198*77=" << russianPeasantMult(198, 77) << endl;
cin.get();
return 0;
}
13. Определить, пересекаются ли 2 отрезка на плоскости, заданные целочисленными координатами начала и конца.
Несмотря на простоту постановки, задача не столь уж тривиальна, если учесть все случаи. Поэтому и ограничимся целочисленными координатами концов отрезков.
//Visual Studio 2015
#include <iostream>
#include <algorithm>
using namespace std;
struct Point { int x; int y; }; //точка
bool onSegment(Point p, Point q, Point r) { // лежит ли точка q на отрезке 'pr'
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;
return false;
}
int orientation(Point p, Point q, Point r) {
//ориентация триплета (p,q,r)
//0 - на одной прямой, 1 - по часовой, 2 - против часовой
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0) ? 1 : 2;
}
bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
//Пересечение отрезков p1-q1 и p2-q2
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
if (o1 != o2 && o3 != o4) return true;
//p1, q1 и p2 на одной прямой и p2 на отрезке p1q1
if (o1 == 0 && onSegment(p1, p2, q1)) return true;
// p1, q1 и q2 на одной прямой и q2 на отрезке p1q1
if (o2 == 0 && onSegment(p1, q2, q1)) return true;
// p2, q2 и p1 на одной прямой и p1 на отрезке p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;
// p2, q2 и q1 на одной прямой и q1 на отрезке p2q2
if (o4 == 0 && onSegment(p2, q1, q2)) return true;
return false;
}
int main() {
struct Point p1 = { 10,0 }, q1 = { 0,10 };
struct Point p2 = { 1,1 }, q2 = { 10,10 };
if (doIntersect(p1, q1, p2, q2)) cout << "Yes";
else cout << "No";
cin.get();
return 0;
}
14. На вход подпрограммы (потока) поступают целые числа. Организовать выбор случайного числа с временной сложностью алгоритма O(1).
Когда-то делал такое на Perl, вот на C++. Но чудес от такого алгоритма не ждите, будут повторы :)
//Visual Studio 2015
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int selectRandom (int x) {
static int res;
static int count = 0; //сколько было чисел
count++;
if (count == 1) res = x; //первое число всегда возвращаем
else { //иначе возвращаем число с вероятностью 1/count
int i = rand() % count;
if (i == count - 1) res = x;
}
return res;
}
int main() {
int stream[] = { 11, 22, 33, 44, 55, 66, 77, 88, 99 };
int n = sizeof(stream) / sizeof(stream[0]);
srand(time(NULL));
for (int i = 0; i < n; i++) {
cout << selectRandom(stream[i]) << endl;
}
cin.get();
return 0;
}
15. Проверить, является ли заданное натуральное число счастливым.
У задачи есть несколько формулировок.
Во-первых, можно считать в смысле последовательности A000959, в русской Вики это описано как очередное "Счастливое число", хотя на самом деле "удачливое" (Lucky), в отличие от "Happy" из этой заметки.
Во-вторых, если мы будем на n-ом шаге вычёркивать каждое (n+1)-ое число, а не число с номером, полученным из n-ого из оставшихся чисел, мы придём несколько к другой последовательности, A000960, связанной с задачей Иосифа Флавия в одной из её формулировок. На этом варианте и остановимся, для надёжности напечатав достаточно длинную цепочку "lucky numbers".
Также, для разнообразия, используем итерации вместо рекурсии (что, вообще говоря, можно сделать всегда, и не рисковать переполнением стека).
//Visual Studio 2015
#include <iostream>
using namespace std;
bool isLucky (int n) {
for (int i = 2; i <= n; i++) {
if (n%i == 0) return false;
n -= n / i;
}
return true;
}
int main() {
for (int i = 1; i <= 3000; i++) {
if (isLucky(i)) cout << i << " ";
}
cin.get();
return 0;
}
17.05.2018, 13:37 [2880 просмотров]