Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.88/17: Рейтинг темы: голосов - 17, средняя оценка - 4.88
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
1

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

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

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

На этой задаче мой решения не проходят по времени. Можно услышать ваше мнение по поводу решения этой задачи?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2011, 11:50
Ответы с готовыми решениями:

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

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

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

Из статики в динамику
Ребят, помогите, пожалуйста переделать этот код динамически. Подскажите, очень...

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

33
Jupiter
Каратель
Эксперт С++
6569 / 3990 / 400
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
11.08.2011, 12:01 2
покажите ваше решение, а мы подправим
0
mac_alleb
7 / 7 / 0
Регистрация: 05.08.2011
Сообщений: 54
11.08.2011, 12:08 3
Я думаю для скорости подойдет Tasm 5.0 . Писать прогу?
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:13  [ТС] 4
Цитата Сообщение от mac_alleb Посмотреть сообщение
Я думаю для скорости подойдет Tasm 5.0 . Писать прогу?
Да, пожалуйста - очень интересно взглянуть.
0
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:16 5
Код и скриншот раоты
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
#include <windows.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
 
int main()
{
    char ch;
    long i,N,K;
    int nCount = -1;
    char str[19];
    do
    {
        printf("Enter numbers:\r\n");
        scanf("%[^\n]",str);
        sscanf(str,"%u %u",&N,&K);
        K = pow(10,K);
        for(i = 1; i < N; i++)
        {
            if(K <= i && i % K == 0)
                nCount++;
        }
        printf("from 1 to %u %d numbers with square %u\r\n",N,nCount + 1,K);
        printf("[Y/N] Y - Enter new numbers\r\n");
        ch = getch();
    }
    while(toupper(ch) == 'Y');
    return 0;
}
0
Миниатюры
Задача на динамику или комбинаторику  
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:23  [ТС] 6
У меня ошибки в программе выдавало, я их исправил, но код медленный - введите для верности 100000000 1. Ограничение времени - 1 секунда.
Вот я исправил:
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
#include <windows.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <ctype.h>
 
int main()
{
        char ch;
        long i,N,K;
        int nCount = -1;
        char str[19];
        do
        {
                printf("Enter numbers:\r\n");
                scanf("%[^\n]",str);
                sscanf(str,"%u %u",&N,&K);
                K = int(pow(float(10),float(K)));
                for(i = 1; i < N; i++)
                {
                        if(K <= i && i % K == 0)
                                nCount++;
                }
                printf("from 1 to %u %d numbers with square %u\r\n",N,nCount + 1,K);
                printf("[Y/N] Y - Enter new numbers\r\n");
                ch = getch();
        }
        while(toupper(ch) == 'Y');
        return 0;
}
Компилятор не брал.
0
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:23 7
Хотя если нужны все числа, даже те у которых нули внутри их записи, то вот такой код пойдёт
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 <windows.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
 
int main()
{
    char ch;
    long i,N,K;
    int nCount = -1;
    char str[19];
    char buf[9];
    char num[9];
    do
    {
        printf("Enter numbers:\r\n");
        scanf("%[^\n]",str);
        sscanf(str,"%u %u",&N,&K);
        sprintf(buf,"%u",pow(10,K));
        
        for(i = 1; i < N; i++)
        {
            sprintf(num,"%u",i);
            if(strstr(num,buf))
                nCount++;
        }
        printf("from 1 to %u %d numbers with square %u\r\n",N,nCount + 1,K);
        printf("[Y/N] Y - Enter new numbers\r\n");
        ch = getch();
    }
    while(toupper(ch) == 'Y');
    return 0;
}
0
Миниатюры
Задача на динамику или комбинаторику  
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:25 8
Цитата Сообщение от Dani Посмотреть сообщение
но код медленный - введите для верности 100000000 1. Ограничение времени - 1 секунда.
- такие моменты нужно сразу оговаривать
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:27  [ТС] 9
Цитата Сообщение от Dani Посмотреть сообщение
код медленный - введите для верности 100000000 1. Ограничение времени - 1 секунда.
Все равно на эти числа не идет - в том то и загвостка что долго работает может комбинаторику подключить?

Добавлено через 32 секунды
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
такие моменты нужно сразу оговаривать
Извиняюсь
0
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:35 10
Цитата Сообщение от Dani Посмотреть сообщение
в том то и загвостка что долго работает
Всё что смог придумать это изменить шаг итерации, время уменьшилось но не до секунды, хотя время выполнения также и от ресурсов ЭВМ зависит
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
#include <windows.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
 
int main()
{
    char ch;
    long i,N,K,step = 1;
    int nCount = -1;
    char str[19];
    char buf[9];
    char num[9];
    do
    {
        printf("Enter numbers:\r\n");
        scanf("%[^\n]",str);
        sscanf(str,"%u %u",&N,&K);
        sprintf(buf,"%u",pow(10,K));
        
        for(i = 1; i < N; i+=step)
        {
            sprintf(num,"%u",i);
            if(strstr(num,buf))
            {
                nCount++;
                if(step == 1)
                    step = pow(10,K);
            }
        }
        printf("from 1 to %u %d numbers with square %u\r\n",N,nCount + 1,K);
        printf("[Y/N] Y - Enter new numbers\r\n");
        ch = getch();
    }
    while(toupper(ch) == 'Y');
    return 0;
}
0
Миниатюры
Задача на динамику или комбинаторику  
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:37  [ТС] 11
Может генерировать сочетания с повторениями?
0
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:38 12
Можеть быть тривиальное решение правильно
Число чисел = N/K ?

Добавлено через 45 секунд
Цитата Сообщение от Dani Посмотреть сообщение
Может генерировать сочетания с повторениями?
Это займёт много времени, думаю не меньше чем простой перебор
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:40  [ТС] 13
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Можеть быть тривиальное решение правильно
Число чисел = N/K ?
Нет. 8 и 1 - 3 должно быть
0
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:41 14
Поразмыслил вот мои сображения:
от 1 до 100-ни - 10-десяток т.е в 100/10 раз меньше, => 100000000 / 10 = 10000000 чисел

Добавлено через 1 минуту
Цитата Сообщение от Dani Посмотреть сообщение
Нет. 8 и 1 - 3 должно быть
в числах от 1-го до 8-ми вообще 10-ти нет или я не правильно понимаю задание?
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:45  [ТС] 15
1 - 1
2 - 10
3 - 11
4 - 100
5 - 101
6 - 110
7 - 111
8 - 1000
Имеющие в двоичной записи 1 нуль: 10, 110,101
0
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 13:32 16
Цитата Сообщение от Dani Посмотреть сообщение
имеющих в двоичной записи ровно K нулей
- недочитал задание, ну так тут нужно в двоичную переводить. Перевод + сравнение и перебор до N да ещё за секунду, думаю это за дольшее время делается....
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 13:36 17
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Перевод + сравнение и перебор до N да ещё за секунду, думаю это за дольшее время делается....
Перебор никак не пройдет.
Тут комбинаторика...
Есть у меня одна идея, попробую реализовать =)
Если пройдет все тесты на acmp - отпишусь.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 14:47  [ТС] 18
Цитата Сообщение от diagon Посмотреть сообщение
Если пройдет все тесты на acmp - отпишусь.
На ацмп у меня 8 тестов прошло обычным перебором, а потом начались жуткие тесты
0
-=ЮрА=-
Заблокирован
Автор 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); 
}
0
Миниатюры
Задача на динамику или комбинаторику  
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 15:35 20
Цитата Сообщение от diagon Посмотреть сообщение
Перебор никак не пройдет.
Тут комбинаторика...
Перебор как раз медленно и надёжно идёт!
Dani, чтобы не загромождать экран закоментируй в моём коде 25-ую строку
C++
1
 printf("bin %s\r\n",buf);
0
11.08.2011, 15:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 15:35

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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