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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.74
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 11:50     Задача на динамику или комбинаторику #1
Условие
Для заданных натуральных чисел N и K требуется вычислить количество чисел от 1 до N, имеющих в двоичной записи ровно K нулей. два натуральных числа через пробел N и K, не превышающие 10^9

На этой задаче мой решения не проходят по времени. Можно услышать ваше мнение по поводу решения этой задачи?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
11.08.2011, 12:01     Задача на динамику или комбинаторику #2
покажите ваше решение, а мы подправим
mac_alleb
7 / 7 / 0
Регистрация: 05.08.2011
Сообщений: 54
11.08.2011, 12:08     Задача на динамику или комбинаторику #3
Я думаю для скорости подойдет Tasm 5.0 . Писать прогу?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:13  [ТС]     Задача на динамику или комбинаторику #4
Цитата Сообщение от mac_alleb Посмотреть сообщение
Я думаю для скорости подойдет Tasm 5.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;
}
Миниатюры
Задача на динамику или комбинаторику  
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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;
}
Компилятор не брал.
-=ЮрА=-
Заблокирован
Автор 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;
}
Миниатюры
Задача на динамику или комбинаторику  
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:25     Задача на динамику или комбинаторику #8
Цитата Сообщение от Dani Посмотреть сообщение
но код медленный - введите для верности 100000000 1. Ограничение времени - 1 секунда.
- такие моменты нужно сразу оговаривать
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:27  [ТС]     Задача на динамику или комбинаторику #9
Цитата Сообщение от Dani Посмотреть сообщение
код медленный - введите для верности 100000000 1. Ограничение времени - 1 секунда.
Все равно на эти числа не идет - в том то и загвостка что долго работает может комбинаторику подключить?

Добавлено через 32 секунды
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
такие моменты нужно сразу оговаривать
Извиняюсь
-=ЮрА=-
Заблокирован
Автор 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;
}
Миниатюры
Задача на динамику или комбинаторику  
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 12:37  [ТС]     Задача на динамику или комбинаторику #11
Может генерировать сочетания с повторениями?
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 12:38     Задача на динамику или комбинаторику #12
Можеть быть тривиальное решение правильно
Число чисел = N/K ?

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

Добавлено через 1 минуту
Цитата Сообщение от Dani Посмотреть сообщение
Нет. 8 и 1 - 3 должно быть
в числах от 1-го до 8-ми вообще 10-ти нет или я не правильно понимаю задание?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 13:32     Задача на динамику или комбинаторику #16
Цитата Сообщение от Dani Посмотреть сообщение
имеющих в двоичной записи ровно K нулей
- недочитал задание, ну так тут нужно в двоичную переводить. Перевод + сравнение и перебор до N да ещё за секунду, думаю это за дольшее время делается....
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 13:36     Задача на динамику или комбинаторику #17
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Перевод + сравнение и перебор до N да ещё за секунду, думаю это за дольшее время делается....
Перебор никак не пройдет.
Тут комбинаторика...
Есть у меня одна идея, попробую реализовать =)
Если пройдет все тесты на acmp - отпишусь.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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); 
}
Миниатюры
Задача на динамику или комбинаторику  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 15:35     Задача на динамику или комбинаторику
Еще ссылки по теме:

В какую область попадает точка, или задача для первокурсника C++
C++ Сложная задача или есть ли в C++ типы с порядком в 30 цифр?
Задача на комбинаторику C++

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

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
Заблокирован
Автор FAQ
11.08.2011, 15:35     Задача на динамику или комбинаторику #20
Цитата Сообщение от diagon Посмотреть сообщение
Перебор никак не пройдет.
Тут комбинаторика...
Перебор как раз медленно и надёжно идёт!
Dani, чтобы не загромождать экран закоментируй в моём коде 25-ую строку
C++
1
 printf("bin %s\r\n",buf);
Yandex
Объявления
11.08.2011, 15:35     Задача на динамику или комбинаторику
Ответ Создать тему
Опции темы

Текущее время: 19:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru