БлогNot. Ещё 15 задач про числа за май 2018-го

Ещё 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 [2792 просмотра]


теги: c++ список числа алгоритм

К этой статье пока нет комментариев, Ваш будет первым