Нарисовать блок схему по исходному коду (C++) #include
#include
#include
#include
using namespace std;
int main()
{
setlocale(LC_ALL, "rus");
ifstream input; // создаем файлы
ofstream output;
int diffr = 1000, m = 1, nod = 0, nod2 = 1, shag = 0, stepalg = 0, i = 0, pr = 0, max = 0, mdiv2 = 0;
int m1, m2, nok, a, b;
input.open("input.txt");
if (!input.is_open())
{
cout << "Ошибка с открытием файла" << endl;
}
else // Если файл успешно открылся
{
int cot[10]; // возьмем 10 чисел
while (input >> pr)
{
cot[i++] = pr; // запишем их в массив
}
for (m = 0; m < 10; m++)
{
if (cot[m] > max) { max = cot[m]; } // найдем максимальное число
}
input.close();
for (pr = 0; pr < i; pr++) {
if (abs(max / 2 - cot[pr]) < diffr) {
diffr = abs(max / 2 - cot[pr]);
mdiv2 = cot[pr]; // нашли максимальное число меньше max/2
}
10;
}
pr = 0;
a = cot[0];
b = cot[1];
while ((a != 0) && (b != 0)) {
if (a > b) { a = a % b; }
else { b = b % a; }
shag++;
}
nod = a + b; // Нод для первых двух чисел
for (pr = 2; pr < i; pr++)
{
while ((nod > 0) && (cot[pr] > 0))
{
if (nod > cot[pr]) { nod = nod % cot[pr]; }
else { cot[pr] = cot[pr] % nod; }
shag++; // окончательное число шагов
}
nod = cot[pr] + nod; // окончательный нод
}
cout << "НОД чисел, которые содержатся в файле: " << endl <<
nod << endl;
cout << "Количество шагов: " << endl << shag << endl;
m1 = max;
m2 = mdiv2;
cout << "Максимальное число (m) равно: " << endl << max << endl
<< "Ближайшее к m/2 число равно: " << endl << mdiv2 << endl;
while (max != 0 && mdiv2 != 0)
{
if (max > mdiv2) { max = max % mdiv2; }
else { mdiv2 = mdiv2 % max; }
}
nod2 = max + mdiv2; // нашли нод максимально числа и ближайшего числа к его половине
nok = (m1 * m2) / nod2; // нашли нок
cout << "НОК(" << m1 << ", " << m2 << ") = " << nok << endl;
// Запишем полученные данные и алгоритм "Решето Эратосфена"
output.open("output.txt");
if (!output.is_open())
{
cout << "Ошибка с открытием файла" << endl;
}
else
{ // файл успешно открылся
int* a = new int[m1 + 1];
for (int i = 0; i < m1; i++)
{
a[i] = i;
}
a[1] = 0;
for (int s = 2; s < m1; s++) {
if (a[s] != 0) {
for (int j = s * 2; j < m1; j += s) {
a[j] = 0;
}
}
}
for (i = 0; i < m1; i++) {
if (a[i] != 0)
{
output << a[i] << endl; // запишем в output все простые числа до max
stepalg++;
}
}
cout << "Шаг - " << stepalg << endl << "Квадратный корень из максимального числа: " << endl << sqrt(m1) << endl;
cout << "Алгоритм 'Решето Эратосфена' в файле output.txt!" << endl;
}
output.close();
}
return 0;
Всего число выбрать K элементов из N равно C_N^K ("цэ из N по K").
Поймем, например, надо ли брать 1-й элемент. Всего сочетаний, где первый элемент взят: C_(N-1)^(K-1) {в самом деле, в этом случае осталось выбрать K-1 из оставшихся N-1}; не взят: C_(N-1)^K. Учитывая, что те, в которые первый элемент входит, идут перед теми, в которые он не входит, решаем: если M > C_(N-1)^(K-1), 1-й элемент не берём, иначе берём.
Дальше если 1-й взяли, M оставляем таким же, если нет - уменьшаем на C_(N-1)^(K-1).
Процесс повторяем, пока не найдем все буквы.
Осталось понять, как считать C_N^K. Исходя из рассуждений выше, C_N^K = C_(N-1)^(K-1) + C_(N-1)^K. Кроме того, C_N^0 = 1 для всех N, C_N^K = 0 при K < 0 или K > N. Пользуясь этим, можно найти все C_N^K. Не забываем про длинную арифметику: C_N^K может не влезать в обычные типы данных. Я буду писать на PascalABC.NET, там длинная арифметика есть - тип BigInteger, если нет - легко найти, как это писать. (Update: в данном случае всё влезет в longint - биномиальные коэффициенты не превысят 10 миллионов с небольшим).
Итак, вот и искомый код:
begin
var N, K: integer;
read(N, K);
var M := ReadString().ToBigInteger();
var C: array[,] of BigInteger := new BigInteger[N, K];
for var j := 1 to K - 1 do
C[0, j] := 0;
for var i := 0 to N - 1 do
C[i, 0] := 1;
for var i := 1 to N - 1 do
for var j := 1 to K - 1 do
C[i, j] := C[i - 1, j] + C[i - 1, j - 1];
var possible := 'a';
while K > 0 do
begin
if M <= C[N - 1, K - 1] then
begin
write(possible);
dec(K);
end
else
M := M - C[N - 1, K - 1];
dec(N);
inc(possible);
end;
end.
Без BigInteger:
begin
var N, K: integer;
var M: longint;
read(N, K, M);
var C: array[,] of longint := new longint[N, K];
for var j := 1 to K - 1 do
C[0, j] := 0;
for var i := 0 to N - 1 do
C[i, 0] := 1;
for var i := 1 to N - 1 do
for var j := 1 to K - 1 do
C[i, j] := C[i - 1, j] + C[i - 1, j - 1];
var possible := 'a';
while K > 0 do
begin
if M <= C[N - 1, K - 1] then
begin
write(possible);
dec(K);
end
else
M := M - C[N - 1, K - 1];
dec(N);
inc(possible);
end;
end.