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

Олимпиадная задача. Не могу найти ошибку - C++

Восстановить пароль Регистрация
 
Roukff
 Аватар для Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 06:27     Олимпиадная задача. Не могу найти ошибку #1
Привет всем! Решил порешать олимпиадные задачи и столкнулся с проблемой: Написанный мной код правильно решает поставленную задачу, но сервер, на котором идет проверка, говорит, мол ответ неправильный на первом же тесте. Это вызвало большие подозрения. Все перепроверил, вроде все правильно. Начал подозревать, что возможно вывод неправильный. Но, вроде бы, тоже все верно. Не могу никак найти ошибку. Цитирую, как надо вводить информацию.

Исходные данные
The first line – a fraction (the first operand);
The second line – the sign of an operation;
The third line – a fraction (the second operand).
Both fractions may be reducible. The numerator is always less than the denominator.

Результат
A single line that contains an irreducible proper fraction (result) in the format described above.

Пример

исходные данные
-3 1/6
+
2/4
результат
-2 2/3

Примеры дробей
Samples of fractional number representation: “-7 3/4”, “8 1/2”, “-7/11”, “0”, “11”.

Код, отвечающий за ввод:

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
//структура дроби
struct Fractional
{
    //объявление целой части, числителя и знаменателя
    long long intPart, numerator, denomerator;
} _oneFract, _twoFract, _result;
 
//функция считывания дроби
Fractional ReadFractional()
{
    Fractional _fract;
    //переменная _razdel определяет, что ввели: только целую часть, только дробную часть или целую и дробную часть
    char _razdel;
    //считываем первое число
    scanf("%lld",&_fract.intPart);
    //считываем разделитель после первой цифры: если нажат Enter, то число без дробной части, 
    //если слеш, то только дробная часть, если пробел то и целая и дробная части присутствуют
    scanf("%c", &_razdel);
    if (_razdel == '\n')
    {
        _fract.numerator = 0;
        _fract.denomerator = 1;
    }
    else if (_razdel == ' ')
    {
        //Считываем дробную часть
        scanf("%lld/%lld%*c", &_fract.numerator, &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
    }
    else if (_razdel == '/')
    {
        //Считываем знаменатель
        scanf("%lld%*c", &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
        _fract.numerator = _fract.intPart;
        _fract.intPart = 0;
    }
    //Сбрасываем входной поток
    fflush(stdin);
    return _fract;
}
Вызов этой функции:
C++
1
2
3
4
5
6
7
8
9
//объявление переменной-знака
    char _sign;
 
    //Считываем первую дробь
    _oneFract = ReadFractional();
    //Считываем знак
    scanf("%c", &_sign);
    //Считываем вторую дробь
    _twoFract = ReadFractional();
Код, отвечающий за вывод результата

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (_result.intPart == 0)
    {
        if (_result.numerator == 0)
        {
            printf("0");
        }
        else
        {
            printf("%lld/%lld", _result.numerator, _result.denomerator);
        }
    }
    else if (_result.numerator == 0)
    {
        printf("%lld",_result.intPart);
    }
    else
    {
        printf("%lld %lld/%lld",_result.intPart, _result.numerator, _result.denomerator);
    }
Также нашел на форуме еще одного человека с похожей проблемой, только он ввод делал через getline(). Вот что он пишет, мб это пригодится для выяснения причины
Strange...I had taken input through getline and removed last character if it was null or end of line. And I was getting wrong answer. But when I changed it to the condition, that remove last character if it is not from 0 to 9, it got AC.
Can anybody explain why?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.08.2012, 06:27     Олимпиадная задача. Не могу найти ошибку
Посмотрите здесь:

C++ Олимпиадная задача
Олимпиадная задача C++
Задача на дп (олимпиадная) C++
C++ Олимпиадная задача
Задача с массивами. Не могу найти ошибку C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
cmath
Модератор
 Аватар для cmath
2415 / 1634 / 132
Регистрация: 11.08.2012
Сообщений: 3,252
Завершенные тесты: 5
16.08.2012, 07:30     Олимпиадная задача. Не могу найти ошибку #2
А полный код можно?
Roukff
 Аватар для Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 07:36  [ТС]     Олимпиадная задача. Не могу найти ошибку #3
Да, без проблем
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include "stdafx.h"
#include <stdio.h>
 
int ABS(int a)
{
    if (a < 0)
        return -a;
    else
        return a;
}
 
//структура дроби
struct Fractional
{
    //объявление целой части, числителя и знаменателя
    long long intPart, numerator, denomerator;
} _oneFract, _twoFract, _result;
 
//функция считывания дроби
Fractional ReadFractional()
{
    Fractional _fract;
    //переменная _razdel определяет, что ввели: только целую часть, только дробную часть или целую и дробную часть
    char _razdel;
    //считываем первое число
    scanf("%lld",&_fract.intPart);
    //считываем разделитель после первой цифры: если нажат Enter, то число без дробной части, 
    //если слеш, то только дробная часть, если пробел то и целая и дробная части присутствуют
    scanf("%c", &_razdel);
    if (_razdel == '\n')
    {
        _fract.numerator = 0;
        _fract.denomerator = 1;
    }
    else if (_razdel == ' ')
    {
        //Считываем дробную часть
        scanf("%lld/%lld%*c", &_fract.numerator, &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
    }
    else if (_razdel == '/')
    {
        //Считываем знаменатель
        scanf("%lld%*c", &_fract.denomerator);
        if (_fract.denomerator == 0)
            _fract.denomerator = 1;
        _fract.numerator = _fract.intPart;
        _fract.intPart = 0;
    }
    //Сбрасываем входной поток
    fflush(stdin);
    return _fract;
}
 
//Функция нахождение наименьшего общего делителя (НОД)
int NOD(int a, int b)
{
    while ((a != 0) && (b != 0))
    {
        (a >= b) ? (a %= b) : (b %= a);
    }
    if (a != 0)
        return a;
    else
        return b;
    //(a != 0) ? (return a) : (return b);
}
 
int main()
{
    //объявление переменной-знака
    char _sign;
 
    //Считываем первую дробь
    _oneFract = ReadFractional();
    //Считываем знак
    scanf("%c", &_sign);
    //Считываем вторую дробь
    _twoFract = ReadFractional();
    
    //НОК
    int _nok = 1;
    if ((_sign == '+') || (_sign == '-'))
    {
        //находим наименьшее общее кратное
        _nok = _oneFract.denomerator * _twoFract.denomerator / NOD(_oneFract.denomerator, _twoFract.denomerator);
        //Умножаем числитель одной дроби на знаменатель другой
        _oneFract.numerator *= _nok / _oneFract.denomerator;
        _twoFract.numerator *= _nok / _twoFract.denomerator;
        //переносим целую часть в числитель
        _oneFract.numerator += _nok * ABS(_oneFract.intPart);
        if (_oneFract.intPart < 0)
        {
            _oneFract.numerator = -_oneFract.numerator;
        }
        _twoFract.numerator += _nok * ABS(_twoFract.intPart);
        if (_twoFract.intPart < 0)
        {
            _twoFract.numerator = -_twoFract.numerator;
        }
    }
    else
    {
        //переносим целую часть в числитель
        _oneFract.numerator += _oneFract.denomerator * ABS(_oneFract.intPart);
        if (_oneFract.intPart < 0)
        {
            _oneFract.numerator = -_oneFract.numerator;
        }
        _twoFract.numerator += _twoFract.denomerator * ABS(_twoFract.intPart);
        if (_twoFract.intPart < 0)
        {
            _twoFract.numerator = -_twoFract.numerator;
        }
    }
        switch (_sign)
        {
            case '+': 
                _result.numerator = _oneFract.numerator + _twoFract.numerator;
                _result.denomerator = _nok;
                break;
            case '-': 
                _result.numerator = _oneFract.numerator - _twoFract.numerator;
                _result.denomerator = _nok; 
                break;
            case '*': 
                _result.numerator = _oneFract.numerator * _twoFract.numerator;
                _result.denomerator = _oneFract.denomerator * _twoFract.denomerator; 
                break;
            case '/': 
                _result.numerator = _oneFract.numerator * _twoFract.denomerator;
                _result.denomerator = _oneFract.denomerator * _twoFract.numerator;
                if (_result.denomerator < 0)
                {
                    _result.numerator = -_result.numerator;
                    _result.denomerator = -_result.denomerator;
                }
                break;
        }
        if (_result.denomerator == 0)
        {
            _result.denomerator = 1;
        }
        //Находим целую часть
        _result.intPart = _result.numerator / _result.denomerator;
        //находим числитель
        _result.numerator %= _result.denomerator;
        if (_result.intPart < 0)
        {
            _result.numerator = ABS(_result.numerator);
            _result.denomerator = ABS(_result.denomerator);
        }
        //Сокращаем дробь
        _nok = _result.denomerator;
        _result.denomerator /= NOD(ABS(_result.numerator), _nok);
        _result.numerator /= NOD(ABS(_result.numerator), _nok);
    //}
 
    if (_result.intPart == 0)
    {
        if (_result.numerator == 0)
        {
            printf("0");
        }
        else
        {
            printf("%lld/%lld", _result.numerator, _result.denomerator);
        }
    }
    else if (_result.numerator == 0)
    {
        printf("%lld",_result.intPart);
    }
    else
    {
        printf("%lld %lld/%lld",_result.intPart, _result.numerator, _result.denomerator);
    }
    return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.08.2012, 09:03     Олимпиадная задача. Не могу найти ошибку #4
Цитата Сообщение от Roukff Посмотреть сообщение
но сервер, на котором идет проверка, говорит, мол ответ неправильный на первом же тесте.
убирайте или закоментируйте перед отправкой строку:
Цитата Сообщение от Roukff Посмотреть сообщение
#include "stdafx.h"
, если отправляете не сам код, а файл (сервер просит указать путь и имя отправляемого на проверку файла), то после того, как убрали данную строку (или закоментировали) не забудьте в компиляторе нажать значек "сохранить".

И на всякий случай (есть и такие проверочные системы), в конце вывода результата сделайте перевод на новую строку:
C
1
printf("\n");
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.08.2012, 09:14     Олимпиадная задача. Не могу найти ошибку #5
Roukff, а может и правда стоит считать построчно. valeriikozlov, как раз тому свидетель, на одном автоматизированном сайте никак не мог понять почему в самой простейшей программе выдаёт ошибки, оказалось у них в тестах на некоторых линиях есть какие-то данные, не относящиеся к задаче
Roukff
 Аватар для Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 09:32  [ТС]     Олимпиадная задача. Не могу найти ошибку #6
stdafx.h я убираю. Попробовал в конце вывода поставить \n. - безрезультатно
А насчет построчного ввода. Подскажите мне, как считать тогда правильно, т.к. у меня не получается.
при считывании дроби может отсутствовать какая-либо часть: либо дробная либо целая...
Обычной строкой
C++
1
scanf("%lld%lld/%lld",one,two,three)
не получается, т.к. ожидает, когда я введу остальные переменные.
Если считывать в строку, то как ее потом грамотно разобрать?
RegExp'ом наврядли получится, птмчт, чтобы его подключить, надо скачивать доп.файлы или я неправ?
Вобщем, подскажите, как тогда грамотно считать эту дробь?
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.08.2012, 09:39     Олимпиадная задача. Не могу найти ошибку #7
Можно попробовать функцией fgets() или C++ функцией std::getline()
Либо тупо считывать по одному символу пока не попадется нужный нам '\n' и после него считывать следующую строку
cmath
Модератор
 Аватар для cmath
2415 / 1634 / 132
Регистрация: 11.08.2012
Сообщений: 3,252
Завершенные тесты: 5
16.08.2012, 10:16     Олимпиадная задача. Не могу найти ошибку #8
Несколько придирок к коду:
1.Почему программа не выдает ошибку для нулевого знаменателя, а приравнивает его к нулю?
2.Почему в программе нет кода, выводящего информацию о вводе дробей и знака операции (формат ввода)? Пользователь не должен эту информацию угадывать.
3.Функция ввода неправильно работает в случае разделяющего знака ' '.
4.Нет кода обрабатывающего ошибки ввода (интересные результаты получаются, особенно в сумме с п.2)
5.Присутствует лишний код (на самом деле находить НОК не нужно, НОД'а вполне хватает)
6.Переносить целую часть в числитель нет смысла (гораздо проще и быстрее представить дробь как целая часть + дробная).
7.Функция нахождения модуля также не нужна (кроме того есть места в коде где для нахождения модуля вы ей не пользуетесь)
8.Не важно: функция main() слишком большая. Попробуйте вынести все вычисления, за исключением элементарных (2+2), в отдельные функции, иначе код тяжело воспринимать, что не есть хорошо. Если будете писать что-то крупнее, сами в своем же коде запутаетесь.

p.s. попробую накидать свой вариант (с учетом выше изложенного) может пригодиться.
Roukff
 Аватар для Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 10:40  [ТС]     Олимпиадная задача. Не могу найти ошибку #9
1. Это я уже просто для уверенности сделал, затем это уберется. Просто в задаче говорится, что ввод корректен и знаменатель нулю не может быть равен.
2. Этот код проверяется автоматом, поэтому там лучше вообще ничего лишнего не выводить
3. А почему не корректно? Объясните пожалуйста
4. он и не нужен, иначе проверящая система выдаст ошибку
5. Это да, лишний код присутствует =) Но вначале надо сделать, чтобы работало, а уже потом оптимизировать
6. а умножать дробь на дробь как будете? мб я забыл что-то о дробях, но вроде целую часть надо в числитель
7. Нет, она как раз таки нужна, т.к. неизвестно, с каким знаком нам подается целая часть и она должна быть положительной
8. Да, это тоже верно, но как я сказал выше, вначале надо сделать, чтоб работало
cmath
Модератор
 Аватар для cmath
2415 / 1634 / 132
Регистрация: 11.08.2012
Сообщений: 3,252
Завершенные тесты: 5
16.08.2012, 16:08     Олимпиадная задача. Не могу найти ошибку #10
На счет ошибки:
Виноват, извиняюсь. Ошибки на самом деле нет. Лишний символ случайно поставил когда занимался отладкой вашего кода. Убрал. Ошибка пропала.
На счет дробей:
Можно перемножать как (ц часть + дробная)*(ц часть + дробная). Надо просто скобки раскрыть.
Что я и сделал. (см. проект).
На счет автомата: Наверное в нем самом ошибка. Сегодня частенько такое встречается.
Если я правильно понял, то он должен
а) либо ввести свои данные в вашу программу и считать результат, затем его проверить (если посылал файл)
б) либо скомпилировать ваш код и все равно проделать пред. пункт
Непонимаю только: как в автомате могут быть какие-то сторонние данные? Он несколько разнотипных задач проверяет??? Какой нормальный человек будет добавлять в программу данные, которые никак не относятся к поставленной для неё цели????
На счет 4 пункта не согласен:
если ваша программа работает без ошибок, то автомат этот не заметит действие кода, обрабатывающего ошибки, в противном случае автомат вас все равно пошлет куда по-дальше, а вы, по крайней мере, будете знать "где собака зарыта".
На счет 7 пункта:
см мою прогу она работает нормально, я ее уже раз 50 протестил (где-то 30 пока отладкой занимался)
я обошелся без всяких модулей.

P. S. Там ввод немного не доработан, но в сообщении, появляющемся после старта программы указано как дроби вводить(от КЭПа ) в остальном все нормально.
Вложения
Тип файла: rar Дроби.rar (2.80 Мб, 3 просмотров)
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
16.08.2012, 22:39     Олимпиадная задача. Не могу найти ошибку #11
C++
1
fflush(stdin);
Это по стандарту undefined behaviour. И даже если оно будет пропускать всё - зачем?! Если stdin - это файл, то получается, что всё после первой дроби - игнорируется?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.08.2012, 23:58     Олимпиадная задача. Не могу найти ошибку
Еще ссылки по теме:

C++ Никак не могу исправить ошибку, задача на функции
Не могу понять ошибку "C2043: недопустимый break". Задача: найти подстроку в строке C++
C++ Задача из Златопольского: "Найти числа с известным количеством делителей". Не могу найти ошибку

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

Или воспользуйтесь поиском по форуму:
Roukff
 Аватар для Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
16.08.2012, 23:58  [ТС]     Олимпиадная задача. Не могу найти ошибку #12
Ура! В соседней ветке мне подсказали, как можно считать ввод: я пропарсил строку и все.
делал я это так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
Fractional ReadFractional()
{
    Fractional _fract;
    char sInput[20];
    gets(sInput);
    switch (sscanf(sInput, "%lld%*c%lld/%lld", &_fract.intPart,&_fract.numerator, &_fract.denomerator))
    {
        case 1: _fract.numerator = 0; _fract.denomerator = 1; break;
        case 2: _fract.denomerator = _fract.numerator; _fract.numerator = _fract.intPart; _fract.intPart = 0; break;
    }
    return _fract;
}
Yandex
Объявления
16.08.2012, 23:58     Олимпиадная задача. Не могу найти ошибку
Ответ Создать тему
Опции темы

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