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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.74
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
#1

Задача на динамику или комбинаторику - C++

11.08.2011, 11:50. Просмотров 2885. Ответов 33
Метки нет (Все метки)

Условие
Для заданных натуральных чисел N и K требуется вычислить количество чисел от 1 до N, имеющих в двоичной записи ровно K нулей. два натуральных числа через пробел N и K, не превышающие 10^9

На этой задаче мой решения не проходят по времени. Можно услышать ваше мнение по поводу решения этой задачи?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2011, 11:50     Задача на динамику или комбинаторику
Посмотрите здесь:
Задача на комбинаторику C++
C++ Задача про фишки на комбинаторику
Задача с фигурой [принадлежит или нет] C++
C++ Ошибка в программе или алгоритме (Задача Океанариум)
Задача:Определить повторяются Цифры в Числе или нет... C++
C++ Сложная задача или есть ли в C++ типы с порядком в 30 цифр?
C++ Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 13:32     Задача на динамику или комбинаторику #16
Цитата Сообщение от Dani Посмотреть сообщение
имеющих в двоичной записи ровно K нулей
- недочитал задание, ну так тут нужно в двоичную переводить. Перевод + сравнение и перебор до N да ещё за секунду, думаю это за дольшее время делается....
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 13:36     Задача на динамику или комбинаторику #17
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Перевод + сравнение и перебор до N да ещё за секунду, думаю это за дольшее время делается....
Перебор никак не пройдет.
Тут комбинаторика...
Есть у меня одна идея, попробую реализовать =)
Если пройдет все тесты на acmp - отпишусь.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 14:47  [ТС]     Задача на динамику или комбинаторику #18
Цитата Сообщение от diagon Посмотреть сообщение
Если пройдет все тесты на acmp - отпишусь.
На ацмп у меня 8 тестов прошло обычным перебором, а потом начались жуткие тесты
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 15:32     Задача на динамику или комбинаторику #19
Цитата Сообщение от Dani Посмотреть сообщение
1 - 1
2 - 10
3 - 11
4 - 100
5 - 101
6 - 110
7 - 111
8 - 1000
Имеющие в двоичной записи 1 нуль: 10, 110,101
Чисел 4 -ри, а не три!
Вот алгоритм, он не быстр зато отрабатывает правильно
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
60
61
62
63
64
#include <windows.h>
#include <stdio.h>
#include <conio.h>
 
void PumpMessages(HWND hWND);
char * num2bin(unsigned long lnum);
 
int main()
{
    HWND hWnd = GetForegroundWindow();
    long N,K,nCount = -1;
    char str[19],*buf;
    do
    {
        printf("Enter numbers:\r\n");
        scanf("%[^\n]",str);
        sscanf(str,"%u %u",&N,&K);
        memset(str,'0',K);
        str[K] = '\0';
        while(0 < N)
        {
            if(strstr(buf = num2bin(N),str))
                nCount++;
            printf("bin %s\r\n",buf);
            N--;
            //Избегаем замерзания программы
            PumpMessages(hWnd);
        }
        printf("%d numbers with square 10^%u\r\n",nCount,K);
    }
    while(toupper(getch()) == 'Y');
    printf("Enter num: ");
    unsigned long lnum;scanf("%u",&lnum);
    printf("%s\r\n",num2bin(lnum));
    getch();
    return 0;
}
 
char * bin = (char *)malloc(sizeof(char));
char * num2bin(unsigned long lnum)
{
    int i = 0;
    do
    {
        bin[i] = '0';
        if(lnum%2)
            bin[i] = '1';
        lnum /= 2;
        if(0 < lnum)
            bin = (char *)realloc(bin,(1 + (i = i + 1))*sizeof(char));
    }
    while(0 < lnum);
    bin[i + 1] = '\0';
    return bin;
}
 
void PumpMessages(HWND hWND)
{
    MSG msg;
    // Handle dialog messages
    while(PeekMessage(&msg, hWND, 0, 0, PM_REMOVE))
        if(!IsDialogMessage(hWND, &msg) && TranslateMessage(&msg))
            DispatchMessage(&msg); 
}
Миниатюры
Задача на динамику или комбинаторику  
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 15:35     Задача на динамику или комбинаторику #20
Цитата Сообщение от diagon Посмотреть сообщение
Перебор никак не пройдет.
Тут комбинаторика...
Перебор как раз медленно и надёжно идёт!
Dani, чтобы не загромождать экран закоментируй в моём коде 25-ую строку
C++
1
 printf("bin %s\r\n",buf);
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 15:39  [ТС]     Задача на динамику или комбинаторику #21
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Чисел 4 -ри, а не три!
Откуда 4?
Какое 4 число?
Ваша программа работает больше 30 секунд (до 30 я считал, а потом надоело )
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 16:00     Задача на динамику или комбинаторику #22
Цитата Сообщение от Dani Посмотреть сообщение
1 - 1
2 - 10
3 - 11
4 - 100
5 - 101
6 - 110
7 - 111
8 - 1000
Имеющие в двоичной записи 1 нуль: 10, 110,101
Внимательно посчитай: 10, 100,101,110,1000 их даже 5 - за это тебе писал, чтобы ты сам обратил внимание что в 8 3 - 5 различных цифр с двоичной записью имеющей нолик. Просмотрев код понял забыл что вначале инициализировал счётчик -1 -цей поэтому вывело 4, их 5!Чтобы было интересно смотреть на экран вывожу анализируемую 2-ную запись взаголвке диалогового окна
C++
1
SetWindowText(hWnd,buf);
, скриншоты в работе и код ниже...
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
60
61
62
63
64
65
#include <windows.h>
#include <stdio.h>
#include <conio.h>
 
void PumpMessages(HWND hWND);
char * num2bin(unsigned long lnum);
 
int main()
{
    HWND hWnd = GetForegroundWindow();
    long N,K,nCount = 0;
    char str[19],*buf;
    do
    {
        printf("Enter numbers:\r\n");
        scanf("%[^\n]",str);
        sscanf(str,"%u %u",&N,&K);
        memset(str,'0',K);
        str[K] = '\0';
        while(0 < N)
        {
            if(strstr(buf = num2bin(N),str))
                nCount++;
            //printf("bin %s\r\n",buf);
            SetWindowText(hWnd,buf);
            N--;
            //Избегаем замерзания программы
            PumpMessages(hWnd);
        }
        printf("%d numbers with square 10^%u\r\n",nCount,K);
    }
    while(toupper(getch()) == 'Y');
    printf("Enter num: ");
    unsigned long lnum;scanf("%u",&lnum);
    printf("%s\r\n",num2bin(lnum));
    getch();
    return 0;
}
 
char * bin = (char *)malloc(sizeof(char));
char * num2bin(unsigned long lnum)
{
    int i = 0;
    do
    {
        bin[i] = '0';
        if(lnum%2)
            bin[i] = '1';
        lnum /= 2;
        if(0 < lnum)
            bin = (char *)realloc(bin,(1 + (i = i + 1))*sizeof(char));
    }
    while(0 < lnum);
    bin[i + 1] = '\0';
    return bin;
}
 
void PumpMessages(HWND hWND)
{
    MSG msg;
    // Handle dialog messages
    while(PeekMessage(&msg, hWND, 0, 0, PM_REMOVE))
        if(!IsDialogMessage(hWND, &msg) && TranslateMessage(&msg))
            DispatchMessage(&msg); 
}
PS: Твои 10000000 выводятся за 3-4 минуты работы, по другому нужна только формула для расчёта, слёту двоичных чисел с нулями и их выводом, всё равно за секунду ни одна программа на обычной машиене тебе не посчитает...
Миниатюры
Задача на динамику или комбинаторику   Задача на динамику или комбинаторику  
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 16:06  [ТС]     Задача на динамику или комбинаторику #23
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Внимательно посчитай: 10, 100,101,110,1000 их даже 5 - за это тебе писал, чтобы ты сам обратил внимание что в 8 3 - 5 различных цифр с двоичной записью имеющей нолик. Просмотрев код понял забыл что вначале инициализировал счётчик -1 -цей поэтому вывело 4, их 5!Чтобы было интересно смотреть на экран вывожу анализируемую 2-ную запись взаголвке диалогового окна
У них у всех k=1 нулей?
у 100 - два нуля, 1000 - 3, а надо 1. Потому что k=1!

Добавлено через 1 минуту
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
PS: Твои 10000000 выводятся за 3-4 минуты работы, по другому нужна только формула для расчёта, слёту двоичных чисел с нулями и их выводом, всё равно за секунду ни одна программа на обычной машиене тебе не посчитает...
Посчитает, только подход другой нужен - в этом я уверен.

Добавлено через 1 минуту
Если есть задача - найдется и решение
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 16:09     Задача на динамику или комбинаторику #24
Цитата Сообщение от Dani Посмотреть сообщение
У них у всех k=1 нулей?
у 100 - два нуля, 1000 - 3, а надо 1. Потому что k=1!
Тогда цикл по N должен выглядеть вот так
C++
1
2
3
4
5
6
7
8
9
10
11
while(0 < N)
        {
            SetWindowText(hWnd,buf);
            if((buf = strstr(num2bin(N),str)))
            if(buf[1] != '0')
                nCount++;
            //printf("bin %s\r\n",buf);
            N--;
            //Избегаем замерзания программы
            PumpMessages(hWnd);
        }
выводит 3 в 8 1, ну на сим удачи тебе в поисках "хорошего" алгоритма...
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 16:27     Задача на динамику или комбинаторику #25
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
удачи тебе в поисках "хорошего" алгоритма...
Удача пригодилась =)
Таки я был прав, треугольник Паскаля рулит!
К сожалению, понятно объяснить вряд ли смогу, сам только сегодня его строить научился, но тем не менее код проходит все тесты практически мгновенно.
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
#include <iostream>
int main(){
    
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    //строим треугольник паскаля
    int pas[33][33] = {};
    pas[0][0] = 1;
    for (int i = 0; i < 33; ++i)
    {
        pas[i][0] = 1;
        pas[i][i] = 1;
        for (int j = 1; j < i ; ++j)
        {
            pas[i][j] = pas[i-1][j-1] + pas[i-1][j];
        }
    }
    
    int n, k;
    std::cin >> n >> k;
    std::string bin;
    
    //переводим число в двоичное представление
    for ( ; n; n >>= 1)
        bin.push_back( (n & 1) + '0');
    
    //подсчитываем количество сочетаний (количество разрядов - 1) по k
    
    int result = 0;
    
    for (size_t i = k + 1; i < bin.size(); ++i)
    {
        result += pas[i-1][k];
    }
    
    //отдельно рассматриваем случай с последним разрядом...
    int zerocount = 0;
    for (int i = bin.size() - 2; i >= 0 && zerocount <= k; --i)
    {
        if (bin[i] == '1')
        {
            if (k - zerocount - 1 >= 0)
            {
                result += pas[i][k - zerocount - 1];
            }
        }
        else
            ++zerocount;
    }
 
    if (zerocount == k)
        ++result;
 
 
    std::cout << result << std::endl;       
}
mac_alleb
7 / 7 / 0
Регистрация: 05.08.2011
Сообщений: 54
11.08.2011, 18:28     Задача на динамику или комбинаторику #26
Набросал программку . Я так понял, главная задача: перевод большого натурального (хотя бы)
числа из десятичного представления в двоичное (хотя бы 32 бит). Моя функция c10to2 это и
делает, причем число бит и размер исходного числа для алгоритма не важны (в демо версии
упрощено до 200 бит). В Chislo1 необходимо ввести побайтно исходное число N. После работы
функций для решения задачи (пока частичного) можно посмотреть регистр BL. В нем будет
число нулевых битов в данном числе (К). Число упаковано в переменную Result в слошную цепочку
битов слева направо. Пока так . Если треба доделать задачу до конца, т.е. состряпать
интерфейсик и процедуру перебора чисел - не проблема, только сообщите .
Вложения
Тип файла: txt nulls.txt (1.9 Кб, 18 просмотров)
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 18:33     Задача на динамику или комбинаторику #27
Цитата Сообщение от mac_alleb Посмотреть сообщение
Набросал программку . Я так понял, главная задача: перевод большого натурального (хотя бы)
числа из десятичного представления в двоичное (хотя бы 32 бит). Моя функция c10to2 это и
делает, причем число бит и размер исходного числа для алгоритма не важны (в демо версии
упрощено до 200 бит). В Chislo1 необходимо ввести побайтно исходное число N. После работы
функций для решения задачи (пока частичного) можно посмотреть регистр BL. В нем будет
число нулевых битов в данном числе (К). Число упаковано в переменную Result в слошную цепочку
битов слева направо. Пока так . Если треба доделать задачу до конца, т.е. состряпать
интерфейсик и процедуру перебора чисел - не проблема, только сообщите .
Перевод числа в двоичную сс на с++ 2 строки занимает, соль не в нем, а в алгоритме.
У вас не получится за секунду перебрать и проверить все возможные числа.
Поэтому эта задача решается комбинаторикой и динамическим программированием.
И да, это сложная олимпиадная задача =)
mac_alleb
7 / 7 / 0
Регистрация: 05.08.2011
Сообщений: 54
15.08.2011, 00:06     Задача на динамику или комбинаторику #28
Покажите мне эти две строчки, да еще для числа произвольной длины . А что каксается задачи
для всех N не превышающих 10^9, то попробую на ассемблере уложится в секунду даже на двушке .
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.08.2011, 07:28     Задача на динамику или комбинаторику #29
Цитата Сообщение от mac_alleb Посмотреть сообщение
Покажите мне эти две строчки, да еще для числа произвольной длины
25-26 в моем коде.
Просто перебор до 10^9 полсекунды примерно занимает, а если еще и переводить каждый раз в двоичную сс и проверять строку, то по времени никак не уложитесь =)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.08.2011, 09:29     Задача на динамику или комбинаторику
Еще ссылки по теме:
В какую область попадает точка, или задача для первокурсника C++
Задача с использованием множества: каких символов в заданной строе больше: русских или латинских? C++
C++ Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0
Python Задача на комбинаторику

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

Или воспользуйтесь поиском по форуму:
mac_alleb
7 / 7 / 0
Регистрация: 05.08.2011
Сообщений: 54
15.08.2011, 09:29     Задача на динамику или комбинаторику #30
За ночку создал алгоритм обратного перевода из двоичной в десятичную для чисел 200-бит (демо
версия). Пришлось "идти" через 16-тиричную систему. Прога наполовину готова. Думаю еще день-два
и выложу. Что касается собственно задачи, то зачем каждый раз переводить в двоичку, можно перевести
один раз, а затем добавлять по 1. Вообще-то тут пахнет 64-битной арифметикой . Если нужны будут
арифметические процедуры для таких чисел сообщите .
Yandex
Объявления
15.08.2011, 09:29     Задача на динамику или комбинаторику
Ответ Создать тему
Опции темы

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