Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перевести с Pascal на С++ . Знатоки http://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++ Шифрование текста в файле проблема в то что в процессе работы программа должна считывать текст в файле и кодировать его. Прога работает нормально,т.е. кодирует декодирует текст при вводе его с клавиатуры, а в файле делает это... http://www.cyberforum.ru/cpp-beginners/thread357189.html
C++ Составьте программу
Составьте программу, проверяющую, образуют ли элементы двумерного массива магический квадрат( в магическом квадрате суммы чисел по всем вертикалям, всем горизонталям и двум диагоналям одинаковы).
C++ Слейте две линейные таблицы А и В в новую таблицу С
Слейте две линейные таблицы А и В в новую таблицу С, поставив элементы таблицы А на нечетные места, а элементы таблицы В - на четные.
C++ Даны коэфициенты квадратного уравнения a,b,c http://www.cyberforum.ru/cpp-beginners/thread357133.html
Даны коэфициенты квадратного уравнения a,b,c. Найти действительные корни этого уравнения.
C++ Сист. Характеристики С++ У меня есть задание : "Напишите фрагмент программы на языке С++, который определяет системные характеристики компьютера и выводит их на экран." я еще новичек в системном программировании, подкиньте... подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.09.2011, 21:26
В общем алгоритм выполнен так:
в массиве 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

и т.д....
3
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru