Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.70/27: Рейтинг темы: голосов - 27, средняя оценка - 4.70
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2

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

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

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

На этой задаче мой решения не проходят по времени. Можно услышать ваше мнение по поводу решения этой задачи?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
11.08.2011, 11:50
Ответы с готовыми решениями:

Задача на комбинаторику
Добрый вечер! Который день пытаюсь решить задачу "Счастливые числа": все знают, что счастливые числа – это те числа, которые содержат...

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

Задача про фишки на комбинаторику
У Андрея есть огромное количество фишек N цветов. Он хочет выложить некоторое количество фишек в один ряд так, чтобы для любых двух...

33
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
11.08.2011, 15:39  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Чисел 4 -ри, а не три!
Откуда 4?
Какое 4 число?
Ваша программа работает больше 30 секунд (до 30 я считал, а потом надоело )
0
Автор FAQ
 Аватар для -=ЮрА=-
6614 / 4256 / 401
Регистрация: 08.08.2009
Сообщений: 10,325
Записей в блоге: 24
11.08.2011, 16:00
Цитата Сообщение от 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 минуты работы, по другому нужна только формула для расчёта, слёту двоичных чисел с нулями и их выводом, всё равно за секунду ни одна программа на обычной машиене тебе не посчитает...
Миниатюры
Задача на динамику или комбинаторику   Задача на динамику или комбинаторику  
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
11.08.2011, 16:06  [ТС]
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Внимательно посчитай: 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 минуту
Если есть задача - найдется и решение
0
Автор FAQ
 Аватар для -=ЮрА=-
6614 / 4256 / 401
Регистрация: 08.08.2009
Сообщений: 10,325
Записей в блоге: 24
11.08.2011, 16:09
Цитата Сообщение от 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, ну на сим удачи тебе в поисках "хорошего" алгоритма...
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 16:27
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
удачи тебе в поисках "хорошего" алгоритма...
Удача пригодилась =)
Таки я был прав, треугольник Паскаля рулит!
К сожалению, понятно объяснить вряд ли смогу, сам только сегодня его строить научился, но тем не менее код проходит все тесты практически мгновенно.
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;       
}
1
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
11.08.2011, 18:28
Набросал программку . Я так понял, главная задача: перевод большого натурального (хотя бы)
числа из десятичного представления в двоичное (хотя бы 32 бит). Моя функция c10to2 это и
делает, причем число бит и размер исходного числа для алгоритма не важны (в демо версии
упрощено до 200 бит). В Chislo1 необходимо ввести побайтно исходное число N. После работы
функций для решения задачи (пока частичного) можно посмотреть регистр BL. В нем будет
число нулевых битов в данном числе (К). Число упаковано в переменную Result в слошную цепочку
битов слева направо. Пока так . Если треба доделать задачу до конца, т.е. состряпать
интерфейсик и процедуру перебора чисел - не проблема, только сообщите .
Вложения
Тип файла: txt nulls.txt (1.9 Кб, 21 просмотров)
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 18:33
Цитата Сообщение от mac_alleb Посмотреть сообщение
Набросал программку . Я так понял, главная задача: перевод большого натурального (хотя бы)
числа из десятичного представления в двоичное (хотя бы 32 бит). Моя функция c10to2 это и
делает, причем число бит и размер исходного числа для алгоритма не важны (в демо версии
упрощено до 200 бит). В Chislo1 необходимо ввести побайтно исходное число N. После работы
функций для решения задачи (пока частичного) можно посмотреть регистр BL. В нем будет
число нулевых битов в данном числе (К). Число упаковано в переменную Result в слошную цепочку
битов слева направо. Пока так . Если треба доделать задачу до конца, т.е. состряпать
интерфейсик и процедуру перебора чисел - не проблема, только сообщите .
Перевод числа в двоичную сс на с++ 2 строки занимает, соль не в нем, а в алгоритме.
У вас не получится за секунду перебрать и проверить все возможные числа.
Поэтому эта задача решается комбинаторикой и динамическим программированием.
И да, это сложная олимпиадная задача =)
1
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
15.08.2011, 00:06
Покажите мне эти две строчки, да еще для числа произвольной длины . А что каксается задачи
для всех N не превышающих 10^9, то попробую на ассемблере уложится в секунду даже на двушке .
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.08.2011, 07:28
Цитата Сообщение от mac_alleb Посмотреть сообщение
Покажите мне эти две строчки, да еще для числа произвольной длины
25-26 в моем коде.
Просто перебор до 10^9 полсекунды примерно занимает, а если еще и переводить каждый раз в двоичную сс и проверять строку, то по времени никак не уложитесь =)
0
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
15.08.2011, 09:29
За ночку создал алгоритм обратного перевода из двоичной в десятичную для чисел 200-бит (демо
версия). Пришлось "идти" через 16-тиричную систему. Прога наполовину готова. Думаю еще день-два
и выложу. Что касается собственно задачи, то зачем каждый раз переводить в двоичку, можно перевести
один раз, а затем добавлять по 1. Вообще-то тут пахнет 64-битной арифметикой . Если нужны будут
арифметические процедуры для таких чисел сообщите .
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
15.08.2011, 10:09
diagon прав. Не нужен здесь перебор.
Надо взять N и посмотреть, сколько битов оно занимает. Например, M битов. Тогда надо считать число сочетаний из M-1 по К. К нулей могут быть в любом порядке среди младших M-1 битов, так как старший бит должен быть 1.
А число сочетаний считается по треугольнику Паскаля.
1
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
15.08.2011, 10:30
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Надо взять N и посмотреть, сколько битов оно занимает. Например, M битов. Тогда надо считать число сочетаний из M-1 по К. К нулей могут быть в любом порядке среди младших M-1 битов, так как старший бит должен быть 1.
Не совсем так, например N = 10001 в двоичной записи и K=2. Если брать все сочетания, то среди них будут
11100,
10110 и т.д.,
а эти числа уже превышают число N.

Добавлено через 12 минут
Этот метод подойдет, если суммировать сочетания
https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
1+C^K_{K+1} +...+C^K_{M-2} + D,

Вот D то как раз и надо ухитриться подсчитать, а D - все числа с K нулями, не превышающие числа N, и со старшим единичным битом на M-ой позиции
2
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
15.08.2011, 12:45  [ТС]
Цитата Сообщение от diagon Посмотреть сообщение
Удача пригодилась =)
Таки я был прав, треугольник Паскаля рулит!
К сожалению, понятно объяснить вряд ли смогу, сам только сегодня его строить научился, но тем не менее код проходит все тесты практически мгновенно.
Проходит даже: https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{19} 1
0
9 / 8 / 1
Регистрация: 05.08.2011
Сообщений: 56
17.08.2011, 05:57
Добил прогу . Выкладываю (рабочая версия, могут быть огрехи ). Как и ранее, числа запакованы
слева направо. В двоичных и 16-тиричных первый байт содержит фактическую длину числа. Вывод
К и времени в 16-тиричке, т.к. лень было доделывать вывод в 10-тичной.
Вложения
Тип файла: txt nulls.txt (8.5 Кб, 68 просмотров)
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
17.08.2011, 05:57

Задача на динамику
На задачу набросал какой-то код, но все варианты он не перебирает. Можете подать какую-нибудь идею, как сделать задачу? #include...

задача на комбинаторику
.Из полной колоды карт вынули две карты, сколько существует вариантов, вынуть карты разной масти? В ответе должно получиться 780.

Задача на комбинаторику
Условие: (Время: 1 сек. Память: 16 Мб Сложность: 63%) Для заданных натуральных чисел N и K требуется вычислить количество чисел от 1 до...

Задача на комбинаторику
Имеется план местности, разбитой на квадраты, заданный матрицей размера NxN. Каждый квадрат имеет высоту относительно уровня моря, значение...

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


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

Или воспользуйтесь поиском по форуму:
34
Ответ Создать тему
Новые блоги и статьи
тв 16 бой ии
anaschu 27.07.2026
Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк
anaschu 27.07.2026
НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .
Очистка реквизитов и табличных частей документа при копировании
Maks 26.07.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил
anaschu 25.07.2026
две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад).
Hrethgir 24.07.2026
В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .
Вот представьте что вам дали бессмертие.
kumehtar 24.07.2026
Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru