Найти минимальное количество операций, необходимое для возведения k в степень n

@Гуру77777 · Регистрация: 14.11.2018

Студворк — интернет-сервис помощи студентам

Кто-нибудь, перепишете на с++ пожалуйста

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var
  N, i, k, count, m: byte;
 
begin
  write('Введите степень: N = ');
  readln(N);
  count := 0;
  m := 0;
  k := 128; //2 в 7-й степени
  { Находим показатели разложения N по степеням 2: }
  for  i := 7 downto 0 do
  begin
    if N and k = k then begin
      if m = 0 then m := i; //Запоминаем наибольшую степень разложения
      inc(count);  //Увеличиваем количество показателей
      //write(i:3);
    end;
    k := k div 2;
  end;
  writeln;
  writeln('Количество вычислений: ', m + count - 1)
end.

@zss · 10.03.2019, 13:50

Зачем переписывать неправильно работающие программы

Сообщение от Гуру77777

if N and k = k then begin

При N не равном нулю - это всегда истина.

Напишите лучше условие задачи.

@Гуру77777 · 10.03.2019, 14:30 **[ТС]**

zss, Задача называется.минимизация количества операций. Найти минимальное количество операций, необходимое для возведения k в степень n. Разрешается использовать операции умножения и возведения в степень, круглые скобки и переменную k. Умножение считается одной операцией, возведению в степень q соответствует q-1 операция

@zss · 10.03.2019, 14:59

Вот функция быстрого возведения в степень
http://www.e-maxx-ru.1gb.ru/algo/binary_pow

C++
1
2
3
4
5
6
7
8
9
10
int binpow (int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1)
            res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}

Остается добавить счетчик, и вуаля:

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>
int binpow(int a, int n,int& count) {
    count = 0;
    int res = 1;
    while (n) {
        if (n & 1)
        {
            res *= a;
            count++;
        }
        a *= a;
          count++;
        n >>= 1;
        count++;
    }
    return res;
}
 
 
int main()
{
    int N, k,count;
    std::cin >> N;
    k = 128;
    int res = binpow(k, N, count);
    std::cout << "Количество вычислений: "<<count;
    return 0;
}

@Гуру77777 · 10.03.2019, 17:35 **[ТС]**

zss, Спасибо

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@Гуру77777 1 / 1 / 0 Регистрация: 14.11.2018 Сообщений: 684
	10.03.2019, 14:30 [ТС]
	zss, Задача называется.минимизация количества операций. Найти минимальное количество операций, необходимое для возведения k в степень n. Разрешается использовать операции умножения и возведения в степень, круглые скобки и переменную k. Умножение считается одной операцией, возведению в степень q соответствует q-1 операция 0

@Гуру77777 1 / 1 / 0 Регистрация: 14.11.2018 Сообщений: 684
	10.03.2019, 17:35 [ТС]
	zss, Спасибо 0

Найти минимальное количество операций, необходимое для возведения k в степень n

Решение