Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.92
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.09.2011, 17:37     Найти количество способов представления заданного числа N в виде суммы степеней двойки #1
Всем привет.

Задача звучит так: Любое натуральное число можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы, различающиеся лишь порядком слагаемых, считаются одинаковыми. Например, для числа 7 таких представлений 6 (4+2+1, 4+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1).

Требуется написать программу, которая найдет количество способов такого представления заданного числа N.

{ссылка на сторонний ресурс, вырезанная модератором}

Может, кто-нибудь ее уже раньше решал, напишите решение пожалуйста.
Я только начинаю решать задачи на тему динамики, и мне важно посмотреть как решается такая задача.

Наброски у меня есть, но у меня не получается избавиться от повторных вариантов, да и решение не красивое.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.09.2011, 17:37     Найти количество способов представления заданного числа N в виде суммы степеней двойки
Посмотрите здесь:

C++ Программа для представления дроби в виде суммы различных дробей.
C++ Вывести таблицу степеней двойки
C++ Разложить число на сумму степеней двойки
Наибольшая целая степень двойки, не превосходящая заданного числа n C++
Рекурсия (алгоритм подсчета числа способов, с помощью которых можно представить число М в виде суммы) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
27.09.2011, 17:40     Найти количество способов представления заданного числа N в виде суммы степеней двойки #2
вам должна помочь формула
http://www.cyberforum.ru/cgi-bin/latex.cgi?2^n-1 = 1 + 2 + ...+ 2^{n-1}
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.09.2011, 17:47  [ТС]     Найти количество способов представления заданного числа N в виде суммы степеней двойки #3
Olga_, но ведь не любое число можно представить в виде http://www.cyberforum.ru/cgi-bin/latex.cgi?2^n-1. И к тому же я не понял, как связать это с самим кол-вом представлений.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.09.2011, 17:49     Найти количество способов представления заданного числа N в виде суммы степеней двойки #4
А по-моему чем-то на это смахивает...
Вместо купюр - степени двойки, меньшие чем число.
Можно сделать похожее, но с массивом пар, кроме текущего значения там еще количество комбинаций будет храниться... Хотя не самое красивое решение по-моему. Лунев за 137 символов написал...
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
27.09.2011, 17:56     Найти количество способов представления заданного числа N в виде суммы степеней двойки #5
Цитата Сообщение от neske Посмотреть сообщение
Olga_, но ведь не любое число можно представить в виде http://www.cyberforum.ru/cgi-bin/latex.cgi?2^n-1. И к тому же я не понял, как связать это с самим кол-вом представлений.
Смотрите. Есть теорема, что любое число натуральное a можно представить в виде суммы
http://www.cyberforum.ru/cgi-bin/latex.cgi?a = a_0+a_12+a_22^2+...+a_n2^n, где все http://www.cyberforum.ru/cgi-bin/latex.cgi?a_i \in \{0,1\} причем данное разложение единственно. Именно набор
http://www.cyberforum.ru/cgi-bin/latex.cgi?(a_n...a_1a_0) и есть двоичное представление числа. Например,
http://www.cyberforum.ru/cgi-bin/latex.cgi?5 = 1+0*2+1*2^2 .

А каждую степень http://www.cyberforum.ru/cgi-bin/latex.cgi?2^k можно, в свою очередь, представить в виде формулы из #2. Вот вам и различное представление в виде степеней двойки.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.09.2011, 19:19  [ТС]     Найти количество способов представления заданного числа N в виде суммы степеней двойки #6
Olga_, пытался понять такое решение, но не получилось.
Вообще, я хотел бы решить ее с помощью динамики, то есть свести задачу к более простой.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.09.2011, 19:32     Найти количество способов представления заданного числа N в виде суммы степеней двойки #7
Цитата Сообщение от neske Посмотреть сообщение
Может, кто-нибудь ее уже раньше решал, напишите решение пожалуйста.
Решал. Держите решение:
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#if defined(_MSC_VER)
#define _CRT_SECURE_NO_DEPRECATE
#endif
 
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
#if defined(__GNUC__)
 
#define __STDC_FORMAT_MACROS
#include <inttypes.h>
 
#elif defined(_MSC_VER)
 
typedef __int64 int64_t;
#define PRId64 "I64d"
#define SCNd64 "I64d"
#endif
int main()
{ 
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
    int N, i,j, mas[10], i_n=0, tmp=1;
    int64_t mas1[1000]={0};
    while(tmp<=1000)
    {
        mas[i_n++]=tmp;
        tmp*=2;
    }
    for(i=0; i<10; i++)
    {
        for(j=999; j>=0; j--)
        {
            if(mas1[j]!=0)
            {
                tmp=mas[i];
                while(j+tmp<1000)
                {
                    mas1[j+tmp]+=mas1[j];
                    tmp+=mas[i];
                }
            }            
        }
        tmp=mas[i];
        while(tmp<=1000)
        {
            mas1[tmp-1]++;
            tmp+=mas[i];
        }
    }
    scanf("%d", &N);
    if(N==0)
        printf("0");
    else
        printf( "%" PRId64, mas1[N-1]); 
  return 0;
}
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.09.2011, 20:24  [ТС]     Найти количество способов представления заданного числа N в виде суммы степеней двойки #8
valeriikozlov, а можно услышать по какому алгоритму вы решали, а то по коду мне не разобрать ход мыслей.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.09.2011, 21:26     Найти количество способов представления заданного числа N в виде суммы степеней двойки #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
В общем алгоритм выполнен так:
в массиве mas1[] расчитываются все значения для N от 1 до 1000 (хотя можно было и расчитывать от 1 до конкретного считанного N). Затем выводится результат для заданного N.
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
29
30
31
32
33
34
35
36
37
38
39
int main()
{ 
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
    int N, i,j, mas[10], i_n=0, tmp=1;
    int64_t mas1[1000]={0};// int64_t  - это то же самое что и long long
    while(tmp<=1000)// в этом цикле в массив mas[] записываем все степени двойки меньше 1000 
    {
        mas[i_n++]=tmp;
        tmp*=2;
    }
    for(i=0; i<10; i++)// вот здесь начинается динамика (см ниже)
    {
        for(j=999; j>=0; j--)
        {
            if(mas1[j]!=0)
            {
                tmp=mas[i];
                while(j+tmp<1000)
                {
                    mas1[j+tmp]+=mas1[j];
                    tmp+=mas[i];
                }
            }            
        }
        tmp=mas[i];
        while(tmp<=1000)
        {
            mas1[tmp-1]++;
            tmp+=mas[i];
        }
    }
    scanf("%d", &N);
    if(N==0)
        printf("0");
    else
        printf( "%" PRId64, mas1[N-1]); 
  return 0;
}
Я покажу на примере N==9.
В массиве mas1[] будут расчитываться значения для различных N (индекс 0 - значение для N==1, индекс 1 для значения N==2 и т.д.)
Изначально mas1[]:
0 1 2 3 4 5 6 7 8 <- индекс массива mas1[]
0 0 0 0 0 0 0 0 0 <- значения массива
C++
1
2
3
4
5
6
7
8
9
10
11
12
       for(j=999; j>=0; j--)
        {
            if(mas1[j]!=0)
            {
                tmp=mas[i];
                while(j+tmp<1000)
                {
                    mas1[j+tmp]+=mas1[j];
                    tmp+=mas[i];
                }
            }            
        }
После этого значения массива mas1[] пока не изменится.
Далее:
C++
1
2
3
4
5
6
      tmp=mas[i];
        while(tmp<=1000)
        {
            mas1[tmp-1]++;
            tmp+=mas[i];
        }
Значения массива mas1[] теперь такое:
0 1 2 3 4 5 6 7 8 <- индекс массива mas1[]
1 1 1 1 1 1 1 1 1 <- значения массива
что означает, что с помощью 1 (первого значения степени двойки) можно создать:
- для N==1 : 1
- для N==2 : 1+1
- для N==3 : 1+1+1
и т.д.

переходим к i==1 (что соответствует следующей степени двойки - 2)
C++
1
2
3
4
5
6
7
8
9
10
11
12
       for(j=999; j>=0; j--)
        {
            if(mas1[j]!=0)
            {
                tmp=mas[i];
                while(j+tmp<1000)
                {
                    mas1[j+tmp]+=mas1[j];
                    tmp+=mas[i];
                }
            }            
        }
После этого значения массива mas1[] теперь такое:
0 1 2 3 4 5 6 7 8 <- индекс массива mas1[]
1 1 2 2 3 3 4 4 5 <- значения массива
Это значит, например для значения по индексу 7 (N==8) (которое стало равно 4), что вариантов сумм 1 и 2 (добавилось 3):
т.е. 2+1+1+1+1+1+1
2+2+1+1+1+1
2+2+2+1+1

Затем:
C++
1
2
3
4
5
6
      tmp=mas[i];
        while(tmp<=1000)
        {
            mas1[tmp-1]++;
            tmp+=mas[i];
        }
После этого значения массива mas1[] теперь такое:
0 1 2 3 4 5 6 7 8 <- индекс массива mas1[]
1 2 2 3 3 4 4 5 5 <- значения массива
Для значения по индексу 7 (N==8) (которое стало равно 5)
добавился вариант:
2+2+2+2

и т.д....
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
27.09.2011, 21:59  [ТС]     Найти количество способов представления заданного числа N в виде суммы степеней двойки #10
Огромнейшее спасибо. Очень благодарен.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
29.09.2011, 15:23  [ТС]     Найти количество способов представления заданного числа N в виде суммы степеней двойки #11
Решил аналогичную задачу, в которой нужно разложить число на всевозможные суммы. Ее я понял хорошо, там рекурсия. Но до сих пор не смог понять, как работает динамика в этой задаче про степени двойки, уж простите )
мне нужно хорошо разобраться в этом, в интернете кстати почти ничего дельного не нашел.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.09.2011, 19:33     Найти количество способов представления заданного числа N в виде суммы степеней двойки #12
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от neske Посмотреть сообщение
мне нужно хорошо разобраться в этом, в интернете кстати почти ничего дельного не нашел.
может быть и такое. Этот алгоритм я придумал сам (когда начинал решать олимпиадные задачи). Не исключаю, что такой алгоритм уже давно придуман и где-то описан (даже уверен что он должен быть придуман), и не исключаю что есть алгоритмы лучше - но до сих пор я пользовался именно этим алгоритмом и всегда он давал мне возможность сдавать все похожие задачи.
Давайте разбираться:
C++
1
2
3
4
5
6
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++
1
2
3
4
5
6
7
8
9
10
11
12
       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++
1
2
3
4
5
6
              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++
1
2
3
4
5
6
     tmp=mas[i];
        while(tmp<=1000)
        {
            mas1[tmp-1]++;
            tmp+=mas[i];
        }
Мы просто добавляем (при i==2) к уже имеющимся вариантам в mas1[] варианты:
просто 4
просто 4+4
просто 4+4+4
и т.д.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
29.09.2011, 23:04  [ТС]     Найти количество способов представления заданного числа N в виде суммы степеней двойки #13
Попробую разобраться, спасибо. Отпишусь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2016, 16:01     Найти количество способов представления заданного числа N в виде суммы степеней двойки
Еще ссылки по теме:

Найти все натуральные числа, не превосходящие числа n, которые можно представить в виде суммы слагаемых C++
C++ Просчитать количество вариантов представления числа в виде суммы натуральных цифр 1, 2 и 3
Найти все представления натурального числа в виде суммы натуральных чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
vailodf
0 / 0 / 0
Регистрация: 14.08.2016
Сообщений: 1
14.08.2016, 16:01     Найти количество способов представления заданного числа N в виде суммы степеней двойки #14
динамика..



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
29
30
31
32
33
34
#include <iostream>
using namespace std;
 
int main() {
  const int pow_N = 10;
  const int N = 1001;
  int dp[pow_N][N];
 
  // для всех `n` используя только 2^0, всего один способ суммы
  for (int j = 0; j < N; ++j)
    dp[0][j] = 1;
 
  // динамика
  for (int i = 1; i < pow_N; ++i){
    for (int j = 0; j < N; ++j){
      int p = 1 << i;
      if (j < p){
        dp[i][j] = dp[i-1][j];
        continue;
      }
      dp[i][j] = 0;
      if (i > 0)
        dp[i][j] += dp[i-1][j];
      if (j-p >= 0)
        dp[i][j] += dp[i][j-p];
    }
  }
 
 
  int n;
  cin >> n;
  cout << dp[9][n];
  return 0;
}

Данная задача очень похожа на задачу нахождение количества способов дать сдачу в определенную сумму имея неограниченный набор монет номиналами в 50, 25, 10, 5 и 1 цент. ("Структура и интерпретация компьютерных программ", раздел 1.2.2)
Yandex
Объявления
14.08.2016, 16:01     Найти количество способов представления заданного числа N в виде суммы степеней двойки
Ответ Создать тему
Опции темы

Текущее время: 07:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru