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

Найти количество способов представления заданного числа 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++ Шифрование текста в файле проблема в то что в процессе работы программа должна считывать текст в файле и кодировать его. Прога работает нормально,т.е. кодирует декодирует текст при вводе его с клавиатуры, а в файле делает это не коректно(такой рандом выдает :)). #include "stdafx.h" #include <string.h> #include <stdlib.h> #include <locale.h> const char alphabet="abcdefghijklmnopqrstuvwxyz"; char mas; int... 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
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.09.2011, 19:33     Найти количество способов представления заданного числа N в виде суммы степеней двойки
Цитата Сообщение от 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
и т.д.
 
Текущее время: 09:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru