Найти количество способов представления заданного числа N в виде суммы степеней двойки - C++ - Ответ 2025555

valeriikozlov · 29.09.2011, 19:33

Сообщение от neske

мне нужно хорошо разобраться в этом, в интернете кстати почти ничего дельного не нашел.

может быть и такое. Этот алгоритм я придумал сам (когда начинал решать олимпиадные задачи). Не исключаю, что такой алгоритм уже давно придуман и где-то описан (даже уверен что он должен быть придуман), и не исключаю что есть алгоритмы лучше - но до сих пор я пользовался именно этим алгоритмом и всегда он давал мне возможность сдавать все похожие задачи.
Давайте разбираться:

C++

tmp=1;
   while(tmp<=1000)// в этом цикле в массив mas[] записываем все степени двойки меньше 1000 
    {
        mas[i_n++]=tmp;
        tmp*=2;
    }

Т.е. в mas[] записаны числа 1, 2, 4, 8 ..... 128, 256, 512
В массиве mas1[] будут расчитываться значения количества представления для различных N (индекс 0 - значение для N==1, индекс 1 для значения N==2 и т.д.)
Допустим сейчас i==2 что означет что мы начинаем работать со степенью двойки равной 4 (до этого мы пробили все варианты со степенью двойки равной 1 и 2 (i было равно 0 и 1))
Например для mas1[7] (N==8) значение равно 5. Т.е. 8 (с помощью 1 и 2) можно набрать 5-тью вариантами:
1+1+1+1+1+1+1+1
2+1+1+1+1+1+1
2+2+1+1+1+1
2+2+2+1+1
2+2+2+2
Теперь мы идем справа налево по массиву mas1[] и натыкаемся в том числе и на mas1[7]:

C++

       for(j=999; j>=0; j--)
        {
            if(mas1[j]!=0)// вот здесь мы наткнулись и на mas1[7]
            {
                tmp=mas[i];
                while(j+tmp<1000)
                {
                    mas1[j+tmp]+=mas1[j];
                    tmp+=mas[i];
                }
            }            
        }

В этом цикле мы начинаем:

C++

              tmp=mas[i];
                while(j+tmp<1000)
                {
                    mas1[j+tmp]+=mas1[j];
                    tmp+=mas[i];
                }

Т.е. tmp сначало равно 4 (когда i==2)
Мы в mas1[7+4], что соответствует N==12 добавляем 5 вариантов mas1[7] с прибавлением к ним 4
Потом tmp равно 8, и мы в mas1[7+8], что соответствует N==16 добавляем 5 вариантов mas1[7] с прибавлением к ним 4+4
и т.д.

Потом:

C++

     tmp=mas[i];
        while(tmp<=1000)
        {
            mas1[tmp-1]++;
            tmp+=mas[i];
        }

Мы просто добавляем (при i==2) к уже имеющимся вариантам в mas1[] варианты:
просто 4
просто 4+4
просто 4+4+4
и т.д.

Вернуться к обсуждению:
Найти количество способов представления заданного числа N в виде суммы степеней двойки C++

Следующий ответ

Другие темы раздела
C++ Перевести с Pascal на С++ . Знатоки https://www.cyberforum.ru/ cpp-beginners/ thread357191.html var a, s: real; begin write('Введите длину стороны квадрата ->'); readln(a); s:=sqr(a); writeln('Площадь квадрата = ', s:6:2); end. var s, d, l, r: real; begin	Шифрование текста в файле C++ проблема в то что в процессе работы программа должна считывать текст в файле и кодировать его. Прога работает нормально,т.е. кодирует декодирует текст при вводе его с клавиатуры, а в файле делает это не коректно(такой рандом выдает :)). #include "stdafx.h" #include <string.h> #include <stdlib.h> #include <locale.h> const char alphabet="abcdefghijklmnopqrstuvwxyz"; char mas; int...
C++ Составьте программу Составьте программу, проверяющую, образуют ли элементы двумерного массива магический квадрат( в магическом квадрате суммы чисел по всем вертикалям, всем горизонталям и двум диагоналям одинаковы). https://www.cyberforum.ru/ cpp-beginners/ thread357140.html	C++ Слейте две линейные таблицы А и В в новую таблицу С Слейте две линейные таблицы А и В в новую таблицу С, поставив элементы таблицы А на нечетные места, а элементы таблицы В - на четные. https://www.cyberforum.ru/ cpp-beginners/ thread357138.html
Даны коэфициенты квадратного уравнения a,b,c C++ Даны коэфициенты квадратного уравнения a,b,c. Найти действительные корни этого уравнения.	C++ Сист. Характеристики С++ https://www.cyberforum.ru/ cpp-beginners/ thread357123.html У меня есть задание : "Напишите фрагмент программы на языке С++, который определяет системные характеристики компьютера и выводит их на экран." я еще новичек в системном программировании, подкиньте пожалуйста материал \ описание как это можно сделать, или порекомендуйте книгу где есть что то подобное.
C++ Учебник по Windows Form Application C++ Подскажите Учебник по Windows Form Application C++. https://www.cyberforum.ru/ cpp-beginners/ thread357122.html	C++ компилятор при запуске программы (программа простая скачал из сайта куда сдавал свои задачи) идет работа программы ,потом через 1 секунду вызывается что "1.pp - обнаружена ошибка. Приложение будет закрыто. Приносим извинения за неудобства.майкрософт извиняется и так далее" я пробовал скачть другие копмпиляторы например Dev ++ , geany под виндовс, visual studio 2010 .Везде одна и таже ошибка. в чем проблема?
C++ Может ли быть ошибка при передаче данных? есть функция: CalculateMovingAverage(&RMSSmoothLenghtM1, URMS.Channel1M, URMSSmooth.Channel1M); такая обработка правильная будет? void __fastcall CalculateMovingAverage(int len, double in, double out) { for (int k = 0; k < len - N; k++) { out = 0; for (int i = 0; i < N; i++) { https://www.cyberforum.ru/ cpp-beginners/ thread357108.html	C++ Base class undefined вот четыре класса. по идее должны работать нормально. но выдают ошибку указанную в названии. и ещё что viewlist не найдет идентификатор. document.h - главный базовый класс. от него наследуется 3 класса. он содержит в себе указатель на голову списка и в своем конструкторе метод для добавления элементов в связный список. #include <string> #include "NODES.h" using namespace std; class... https://www.cyberforum.ru/ cpp-beginners/ thread357070.html
Конфликт имени функции в шаблоне C++ template <class x> x plus(const x &x1, const x &x2) { return x1+x2; } int main(int argc, char argv, char env) { system("clear"); int a=10,b=37; std::string s1="111",s2="222"; std::cout<<plus(111,222)<<std::endl;	C++ Как объявить строковую переменную? которой в процессе выполнения программы будут присваиваться разные значения. Вот это: char* a = "VasiaPupkin"компилятор объявляет устаревшим: warning: deprecated conversion from string constant to 'char' https://www.cyberforum.ru/ cpp-beginners/ thread357044.html

	29.09.2011, 19:33

Найти количество способов представления заданного числа N в виде суммы степеней двойки - C++ - Ответ 2025555

Решение