Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A). У вершины Г предками являются А и В, значит индекс вершины Г равен 1+1=2. И т.д.
#include <iostream> // подключаем библиотеку ввода-вывода
using namespace std; // объявляем пространство имен std
void insertSort(int[], int); // прототип функции сортировки
int main() // функция main выполняется первой
{
setlocale(LC_CTYPE, "Russian"); // русифицируем вывод
cout << "Введите кол-во элементов: ";
int p;
cin >> p;
int *k = new int[p]; // объявляем одномерный массив
cout << "Одномерный массив:" << endl;
for (int i = 0; i < p; i++)
{
k[i] = 5 + rand() % 40; //заполняем массив случайными числами
cout << "k[" << i << "] = " << k[i] << endl; // выводим массив
}
cout << endl;
cout << "Сортировка массива вставками по убыванию:"<<endl;
insertSort(k, p); // сортируем массив
for (int i = 0; i < p; i++)
{
cout << "k[" << i << "] = " << k[i] << endl; // выводим массив
}
cout << endl;
delete[]k;
return 0; // успешное окончание программы
} // конец функции main
// функция сортировки вставками по убыванию
void insertSort(int c[], int d)
{ // c[] - массив для сортировки, d - количество элементов массива
int save, // переменная для хранения элемента сортируемого массива
iPred; // индекс предыдущего элемента
// цикл алгоритма начинается с 1-го элемента
// поскольку массив, состоящий из одного элемента является
// отсортированным и уже относительно него вставляются остальные
for (int i = 1; i < d; i++)
{
save = c[i]; // инициализируем переменную текущим значением элемента
iPred = i - 1; // запоминаем индекс предыдущего элемента массива
//вложенный цикл ищет место для вставки, меняя местами элементы c[iPred+1] и c[iPred]
while (iPred >= 0 && c[iPred] < save)
{
c[iPred + 1] = c[iPred]; // переставляем элемент массива
c[iPred] = save; // через save
iPred--; // декрементируем индекс iPred
}
}
}
Объяснение:
ответ: 14
Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A). У вершины Г предками являются А и В, значит индекс вершины Г равен 1+1=2. И т.д.
Объяснение: