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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
#1

Счастливый билет. Надо сократить время работы программы - C++

02.11.2013, 20:10. Просмотров 1769. Ответов 30
Метки нет (Все метки)

Написал 2 программы обе работают очень долго первая 19сек вторая 15сек
А надо: Лимит времени 2000/4000/4000/4000 мс.

Условие: Надо ввести число в диапазоне 10000000 ≤ M < N ≤ 99999999. Посчитать количество счастливых билетов
Примеры:
Input: 11111110 11111112
Output: 1
Input: 10000000 99999999
Output: 4379055

Вот код первой задачи:
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
#include <iostream>
using namespace std;
void func(unsigned long *a, unsigned long *b)
{
    unsigned long counter=0;
    unsigned long A, B, C, D, E, F, G, H, X, Y;
    for(unsigned long i=*a; i<=*b; i++)
    {
        A=i/10000000;
        B=(i/1000000)%10;
        C=(i/100000)%10;
        D=(i/10000)%10;
        E=(i/1000)%10;
        F=(i/100)%10;
        G=(i/10)%10;
        H=i%10;
 
        X=A+B+C+D;
        Y=E+F+G+H;
 
        if (X==Y)
            {
                counter++;
            }
    }
 
    cout<<counter;
}
int main()
{
    unsigned long a, b;
    cin>>a>>b;
    func(&a, &b);
    return 0;
}
Вот код второй задачи:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
void func(unsigned long *a, unsigned long *b)
{
    unsigned long counter=0;
    for(unsigned long i=*a;i<=*b; i++)
    {
        if(((i/10000000)+((i/1000000)%10)+((i/100000)%10)+((i/10000)%10))==(((i/1000)%10)+((i/100)%10)+((i/10)%10)+(i%10)))
            counter++;
    }
 
    cout<<counter;
}
int main()
{
    unsigned long a, b;
    cin>>a>>b;
    func(&a, &b);
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2013, 20:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Счастливый билет. Надо сократить время работы программы (C++):

Как сократить время работы программы?! - C++
Нужно сократить время работы программы по вычислению чисел Фибоначчи: Вот мой код: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include...

Счастливый билет - C++
Ув. программисты, помогите пожалуйста несчастному студенту решить задачу. (о вознаграждении договоримся) Дан массив из 6 целых чисел от...

Счастливый билет! - C++
билет с шестизначным номером считается счастливым если сумма трех старших цифр совпадает с суммой трех младших. допустим что в билетной...

счастливый билет - C++
нам дается номер билета ,нужно проверить ,если мы будем разделять этот номер ,сумма цифр до раздела должна быть равна сумме цифр после...

счастливый билет - C++
Вводится шестизначное число .Определить является ли билет с этим номером счастливым ?с оптимизацией времени решения на турбо си!прошу...

Счастливый билет - C++
Всем привет помогите с решением задачи.Вводится шестизначное число .Определить является ли билет с этим номером счастливым ?Нужно...

30
zitxbit
88 / 740 / 75
Регистрация: 11.04.2012
Сообщений: 971
02.11.2013, 20:12 #2
Программы с бинарной арифметикой лучше всего писать на ассемблере.
0
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
02.11.2013, 20:16  [ТС] #3
Цитата Сообщение от zitxbit Посмотреть сообщение
Программы с бинарной арифметикой лучше всего писать на ассемблере.
Ассемблер - это другой язык программирования? Мне именно в с++ надо
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.11.2013, 20:53 #4
FoxTails, у вас цикл слишком долго считает (100 млн. итераций). ваше решение задачи "в лоб" не годится. задачу можно решить за 20 тыс. итераций. попробуйте разбить задачу на меньшие подзадачи.
0
FoxTails
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 10
02.11.2013, 22:24  [ТС] #5
Цитата Сообщение от ya_noob Посмотреть сообщение
FoxTails, у вас цикл слишком долго считает (100 млн. итераций). ваше решение задачи "в лоб" не годится. задачу можно решить за 20 тыс. итераций. попробуйте разбить задачу на меньшие подзадачи.
можете написать, что то не получается
0
Хулиган
85 / 80 / 12
Регистрация: 08.08.2012
Сообщений: 737
02.11.2013, 22:35 #6
что такое счастливый билет?
0
Alex5
1056 / 720 / 108
Регистрация: 12.04.2010
Сообщений: 1,847
02.11.2013, 22:43 #7
Вместо того, чтобы вычислять A, B, C, D, E, F, G, H на каждом шаге цикла, можно сделать это только один раз - перед входом в цикл.
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
void func2(unsigned long *a, unsigned long *b)
{
    unsigned long counter=0;
    unsigned long A, B, C, D, E, F, G, H, X, Y;
 
    unsigned long i=*a;
    A=i/10000000;
    B=(i/1000000)%10;
    C=(i/100000)%10;
    D=(i/10000)%10;
    E=(i/1000)%10;
    F=(i/100)%10;
    G=(i/10)%10;
    H=i%10;
 
    for( ; i<=*b; i++)
    {
        X=A+B+C+D;
        Y=E+F+G+H;
 
        if (X==Y)
        {
            counter++;
        }
        Next( A, B, C, D,   E, F, G, H );
    }
 
    cout<<counter;
 
}
А в функции Next() реализовать "сложение столбиком" - к числу ABCDEFGH прибавить 1.
0
ValeryS
Модератор
6653 / 5062 / 470
Регистрация: 14.02.2011
Сообщений: 16,928
02.11.2013, 22:51 #8
Цитата Сообщение от zitxbit Посмотреть сообщение
Программы с бинарной арифметикой лучше всего писать на ассемблере.
во первых где ты увидел в этой задаче бинарную арифметику
во вторых чтобы соревноваться современными оптимизаторами, надо знать процессор "на зубок", распараллеливание команд, порядок доступа к кэшу, и много еще чего,как ты напишешь деление на 10?
в третьих программа на ассемблере не переносима

FoxTails,
раздели цикл на 2 по 10000
старшая часть и младшая
вторая подсказка сумма четырех цифр от 1 до 36
0
Tulosba
:)
Эксперт С++
4396 / 3232 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
02.11.2013, 22:56 #9
Цитата Сообщение от ValeryS Посмотреть сообщение
вторая подсказка сумма четырех цифр от 1 до 36
а 0 куда делся?
0
ValeryS
Модератор
6653 / 5062 / 470
Регистрация: 14.02.2011
Сообщений: 16,928
02.11.2013, 22:59 #10
Цитата Сообщение от Tulosba Посмотреть сообщение
а 0 куда делся?
ты где нибудь видел билет
0000ХХХХ?????
в любом случае если билет 8 значный начинается с 1 в старшем разряде
может где нибудь и есть билеты с незначащими 0, но я не встречал
0
Tulosba
:)
Эксперт С++
4396 / 3232 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
02.11.2013, 23:12 #11
Цитата Сообщение от ValeryS Посмотреть сообщение
ты где нибудь видел билет
0000ХХХХ?????
в классических трамваях билеты вообще 6 значные. И да, они могут начинаться с нуля. Правда по условию задачи ТС начинаются с 1. Однако же из фразы
Цитата Сообщение от ValeryS Посмотреть сообщение
вторая подсказка сумма четырех цифр от 1 до 36
не ясно про какие цифры идет речь (первые, последние или еще какие).
0
ValeryS
Модератор
6653 / 5062 / 470
Регистрация: 14.02.2011
Сообщений: 16,928
02.11.2013, 23:21 #12
Цитата Сообщение от Tulosba Посмотреть сообщение
И да, они могут начинаться с нуля.
хорошо принимается
Цитата Сообщение от Tulosba Посмотреть сообщение
не ясно про какие цифры идет речь (первые, последние или еще какие).
ладно расшифровываю
создаем массив на 37 элементов 0-36 обнуляем его
крутим чикл от 0 до 9999 это старшие 4 числа
подсчитываем сумму
ячейку массива с индексом равным сумме увеличиваем на 1
C++
1
arr[summ]++;
крутим цикл от 0 до 9999 это младшие 4 числа
подсчитываем сумму
обращаемся к ячейке с индексом равным сумме
если она равна 0 ничего не делаем
если нет уменьшаем значение на 1
количество билетов увеличиваем на 1
C++
1
2
3
4
5
if(arr[summ])
 {
  arr[summ]--;
  count++;
 }
правда необходимо "доработать напильником" для условий ТС
0
Alex5
1056 / 720 / 108
Регистрация: 12.04.2010
Сообщений: 1,847
02.11.2013, 23:43 #13
Цитата Сообщение от ValeryS Посмотреть сообщение
крутим цикл от 0 до 9999
А если задан диапазон значений a == 12345678, b == 34566543, то в каких пределах крутить циклы?
Цитата Сообщение от ValeryS Посмотреть сообщение
если нет уменьшаем значение на 1
Например, 11114000, 11110400, 11110040, 11110004. Эти билеты счастливые. А если мы сразу уменьшаем на 1, то мы не досчитаемся многих билетов.

Добавлено через 3 минуты
Цитата Сообщение от ValeryS Посмотреть сообщение
ладно расшифровываю
создаем массив на 37 элементов 0-36 обнуляем его
крутим чикл от 0 до 9999 это старшие 4 числа
подсчитываем сумму
ячейку массива с индексом равным сумме увеличиваем на 1
Код C++
1
arr[summ]++;
Что же касается диапазона от 00000000 до 99999999, то дальше не нужны никакие циклы. Число счастливых билетов равно сумме квадратов элементов массива arr[].
0
ValeryS
Модератор
6653 / 5062 / 470
Регистрация: 14.02.2011
Сообщений: 16,928
02.11.2013, 23:47 #14
Alex5,
ну я же сказал
Цитата Сообщение от ValeryS Посмотреть сообщение
"доработать напильником"
это же просто идея, возражения принимаются
Цитата Сообщение от Alex5 Посмотреть сообщение
Например, 11114000, 11110400, 11110040, 11110004.
хорошо давай не будем вычитать
нашим проще
уйдет ветвление

тогда в первом цикле
C++
1
arr[summ]=1;
во втором
C++
1
count+=arr[summ];
Добавлено через 1 минуту
Цитата Сообщение от Alex5 Посмотреть сообщение
Что же касается диапазона от 00000000 до 99999999, то дальше не нужны никакие циклы. Число счастливых билетов равно сумме квадратов элементов массива arr[].
не понял
переведи
0
Alex5
1056 / 720 / 108
Регистрация: 12.04.2010
Сообщений: 1,847
03.11.2013, 00:20 #15
ValeryS,
Цитата Сообщение от ValeryS Посмотреть сообщение
не понял
переведи
Так вот, ты сам написал:
Цитата Сообщение от ValeryS Посмотреть сообщение
Код C++
1
count+=arr[summ];
В случае диапазона билетов от 00000000 до 99999999 эта операция будет выполнена arr[summ] раз. ( Сколько раз во втором цикле встретится билет с суммой summ? arr[summ] раз. )

Рассмотрим билеты с 4 цифрами ( от 0000 до 9999 ).
Сколько случаев, когда сумма старших цифр равна 2?
02 11 20 arr[2] == 3
Сколько счастливых билетов, у которых сумма старших цифр равна сумме младших цифр и равна 2?
0202
0211
0220
1102
1111
1120
2002
2011
2020
9 билетов == arr[2]*arr[2]

Добавлено через 6 минут
ValeryS,
Цитата Сообщение от ValeryS Посмотреть сообщение
не понял
переведи
Так вот, ты сам написал:
Цитата Сообщение от ValeryS Посмотреть сообщение
Код C++
1
count+=arr[summ];
В случае диапазона билетов от 00000000 до 99999999 эта операция будет выполнена arr[summ] раз. ( Сколько раз во втором цикле встретится билет с суммой summ? arr[summ] раз. )

Рассмотрим билеты с 4 цифрами ( от 0000 до 9999 ).
Сколько билетов, у которых сумма старших цифр равна 2 ? 02 11 20 arr[2] == 3
Сколько счастливых билетов, у которых сумма старших цифр равна сумме младших цифр и равна 2?
0202
0211
0220
1102
1111
1120
2002
2011
2020
9 билетов == arr[2]*arr[2]
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 00:20
Привет! Вот еще темы с ответами:

Почти счастливый билет - C++
В гугле полно задач про &quot;Счастливые билеты&quot;, а у меня возникла проблема с &quot;Почти счастливыми билетами. Вот задача - Назовем “почти...

Задача на счастливый билет - C++
Определить , является ли заданное с клавиатуры шестизначное число четным , счастливым (сумма первых трех цифр равна сумме последних трех...

Счастливый билет (Лимит Времени) - C++
Всем привет! Контестер пишет Time Limit. Подскажите что можно сделать чтоб моя программа работала быстрее. Что можно изменить или добавить?...

Задача про счастливый билет - C++
Добрый день, только начинаю постигать азы, решила начать с практики, ну и конечно знаменитая задача про счастливый билет... алгоритм уж...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
03.11.2013, 00:20
Ответ Создать тему
Опции темы

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