Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.91/11: Рейтинг темы: голосов - 11, средняя оценка - 4.91
1 / 1 / 1
Регистрация: 02.12.2013
Сообщений: 30
1

Переполнение стека

25.01.2016, 19:47. Просмотров 1999. Ответов 9
Метки нет (Все метки)

Добрый вечер!
Я пытался решить следующую задачку:

Кликните здесь для просмотра всего текста
Петя и Вася часто играют в различные логические игры. Недавно Петя поведал Васе о новой игре «Быки и коровы» и теперь они играют в эту игру сутками. Суть игры очень проста: Петя загадывает четырехзначное число, состоящее из различных цифр. Вася отгадывает задуманное Петей число, перебирая возможные варианты. Каждый раз Вася предлагает вариант своего числа, а Петя делает Васе подсказку: сообщает количество быков и коров, после чего Вася с учетом подсказки продолжает отгадывание числа до тех пор, пока не отгадает. Быки – это количество цифр в предложенном Васей числе, совпадающих по значению и стоящих в правильной позиции в задуманном Петей числе. Коровы – количество цифр, совпадающих по значению, но находящихся в неверной позиции. Например, если Петя задумал число 5671, а Вася предложил вариант 7251, то число быков равно 1 (только цифра 1 на своем месте), а число коров равно 2 (только цифры 7 и 5 не на своих местах). Петя силен в математике, но даже он может ошибаться. Помогите Пете написать программу, которая бы по загаданному Петей и предложенному Васей числам сообщала количество быков и коров.

Входные данные
Кликните здесь для просмотра всего текста
В единственной строке входного файла INPUT.TXT записано два четырехзначных натуральных числа A и B через пробел, где А – загаданное Петей число, а В – предложенный Васей вариант
.

Выходные данные
Кликните здесь для просмотра всего текста
В выходной файл OUTPUT.TXT нужно вывести два целых числа через пробел — количество быков и коров.


Примеры
№ INPUT.TXT OUTPUT.TXT
1 5671 7251 1 2
2 1234 1234 4 0
3 2034 6234 2 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <fstream>
using namespace std; int z; int PetyaArray[4]; int VasyaArray[4]; 
void PetyaSort(int n, int z)
{
 
    int d = n % 10;
    do {
        PetyaSort(n / 10, z - 1);
        PetyaArray[z] = d;
    } while (-1 < z < 4);
}
void VasyaSort(int n, int z)
{
 
    int d = n % 10;
    do {
        VasyaSort(n / 10, z - 1);
        VasyaArray[z] = d;
    } while (-1 < z < 4);
 
}
int main() {
    int Byki; int Korovy; Byki = 0; Korovy = 0; int Petya; int Vasya; z = 3;
    ifstream fin("INPUT.TXT");
    ofstream fout("OUTPUT.TXT");
    if (fin) {
            fin >> Petya;
            fin >> Vasya;
    }
    else
        cout << "ERROR OPENING FILE111!!11";
    PetyaSort(Petya, z);
    VasyaSort(Vasya, z);
 
    for (int i = 0; i < 4; ++i)
        for (int j = 0; i < 4; ++i)
        {
            if (PetyaArray[i] == VasyaArray[i])
                Byki = Byki + 1;
            else
                if (PetyaArray[i] == VasyaArray[j])
                    Korovy = Korovy + 1;
        }
    fout << Byki << ' ';
    fout << Korovy << ' ';
    system("pause");
    return 0;
}
Проблема: происходит переполнение стека в функциях PetyaSort и VasyaSort . (хотя оператор do/while должен был исправить это)
Можете помочь мне это исправить?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.01.2016, 19:47
Ответы с готовыми решениями:

Переполнение стека
Хочу полюбопытствовать. Вычитал недавно, что на стек выделяется ограниченная область памяти, и в...

Переполнение стека
Всем добрый вечер. Я создаю вектор, который имеет большой размер: порядка 256000000. Этот вектор...

Переполнение стека
Есть функция f(): void f() { //... std::make_pair&lt;size_t, size_t&gt; pairReturner(); //... } ...

Переполнение стека
Привет народ. Такой вопрос: Если в общем виде: if (условие) double d else double d почему...

9
Native x86
Эксперт Hardware
3510 / 2329 / 686
Регистрация: 13.02.2013
Сообщений: 7,661
25.01.2016, 19:49 2
Какая любопытная запись условия:
Код
while (-1 < z < 4)
Кто вас такому научил?
1
1 / 1 / 1
Регистрация: 02.12.2013
Сообщений: 30
25.01.2016, 19:51  [ТС] 3
Цитата Сообщение от quwy Посмотреть сообщение
Какая любопытная запись условия:
CodeВыделить код
1
while (-1 < z < 4)
Кто вас такому научил?
Да никто.
Таким образом я попытался реализовать условие, что подаётся на вход только четырёхзначное число. (ну и 4 ячейки массива выделены под это дело)
1
Эксперт С++
4964 / 3070 / 456
Регистрация: 10.11.2010
Сообщений: 11,159
Записей в блоге: 10
25.01.2016, 19:51 4
Цитата Сообщение от roman0412 Посмотреть сообщение
Можете помочь мне это исправить?
Избавься от локальных переменных внутри рекурсивных функций. Если не поможет - избавься от рекурсии. Если не поможет - ищи ошибку в посте №2.
1
Native x86
Эксперт Hardware
3510 / 2329 / 686
Регистрация: 13.02.2013
Сообщений: 7,661
25.01.2016, 19:55 5
Цитата Сообщение от roman0412 Посмотреть сообщение
Таким образом я попытался реализовать условие, что подаётся на вход только четырёхзначное число. (ну и 4 ячейки массива выделины под это дело)
Это условие работает так: сначала вычисляется значение -1 < z, которое будет равно либо TRUE, либо FALSE в зависимости от значения z. А потом этот результат поступает как левая часть в выражение < 4. А т.к. FALSE приводится к 0, а TRUE соответственно к 1, условие получается всегда истинным (и 0 и 1 меньше 4), ваш цикл становится бесконечным, а значит и рекурсия становится бесконечной, в итоге переполнение стека.
2
Эксперт С++
4964 / 3070 / 456
Регистрация: 10.11.2010
Сообщений: 11,159
Записей в блоге: 10
25.01.2016, 20:02 6
Всё верно. Так условие не пишется.
Для условия -1 < z < 4 - while ( -1 < z && z < 4 )
Для условия что число четырёхзначное: while ( z > -10000 && z < 10000 )
А в исходном условии получается бесконечная рекурсия, из-за чего и происходит переполнение стека.
0
1 / 1 / 1
Регистрация: 02.12.2013
Сообщений: 30
25.01.2016, 20:02  [ТС] 7
Цитата Сообщение от quwy Посмотреть сообщение
Это условие работает так: сначала вычисляется значение -1 < z, которое будет равно либо TRUE, либо FALSE в зависимости от значения z. А потом этот результат поступает как левая часть в выражение < 4. А т.к. FALSE приводится к 0, а TRUE соответственно к 1, условие получается всегда истинным (и 0 и 1 меньше 4), ваш цикл становится бесконечным, а значит и рекурсия становится бесконечной, в итоге переполнение стека.
Спасибо.
Я попробовал сделать так:
while (z > -1 && z < 4);
Мой новый метод тоже не сработал. (рекурсия никуда не делась) Можете объяснить почему?
0
Эксперт С++
3206 / 1733 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2016, 22:04 8
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
//Петя и Вася часто играют в различные логические игры. Недавно Петя поведал
//Васе о новой игре «Быки и коровы» и теперь они играют в эту игру сутками.
//Суть игры очень проста: Петя загадывает четырехзначное число,
//состоящее из различных цифр. Вася отгадывает задуманное Петей число,
//перебирая возможные варианты. Каждый раз Вася предлагает вариант своего числа,
//а Петя делает Васе подсказку: сообщает количество быков и коров, после чего
//Вася с учетом подсказки продолжает отгадывание числа до тех пор, пока
//не отгадает. Быки – это количество цифр в предложенном Васей числе,
//совпадающих по значению и стоящих в правильной позиции в задуманном Петей числе.
//Коровы – количество цифр, совпадающих по значению, но находящихся в неверной
//позиции. Например, если Петя задумал число 5671, а Вася предложил вариант 7251,
//то число быков равно 1 (только цифра 1 на своем месте), а число коров равно 2
//(только цифры 7 и 5 не на своих местах). Петя силен в математике, но даже
//он может ошибаться. Помогите Пете написать программу, которая бы по загаданному
//Петей и предложенному Васей числам сообщала количество быков и коров.
 
//Входные данные
//В единственной строке входного файла INPUT.TXT записано два четырехзначных
//натуральных числа A и B через пробел, где А – загаданное Петей число,
//а В – предложенный Васей вариант.
 
//Выходные данные
//В выходной файл OUTPUT.TXT нужно вывести два целых числа через пробел —
//количество быков и коров.
 
//Примеры
//№ INPUT.TXT OUTPUT.TXT
//1 5671 7251 1 2
//2 1234 1234 4 0
//3 2034 6234 2 1
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <utility>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef std::pair   < int,  int     >   T_bulls_and_cows;
///////////////////////////////////////////////////////////////////////////////
T_bulls_and_cows    get_bulls_and_cows
    (
        T_str   A,
        T_str   B
    )
{
    T_bulls_and_cows    res;
    T_str               diff;
 
    std::transform
        (
            A.begin             (),
            A.end               (),
            B.begin             (),
            std::back_inserter  ( diff ),
            std::minus<char>    ()
        );
 
    res.first   =   std::count
                        (
                            diff.begin  (),
                            diff.end    (),
                            char        ()
                        );
 
    std::sort(  A.begin(),  A.end()     );
    std::sort(  B.begin(),  B.end()     );
 
    T_str   intersection;
 
    std::set_intersection
        (
            A.begin             (),
            A.end               (),
            B.begin             (),
            B.end               (),
            std::back_inserter  ( intersection )
        );
 
    res.second  =       intersection.size()
                    -   res.first;
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_str   A{};
    T_str   B{};
 
    std::cin    >>  A
                >>  B;
 
    auto    bulls_and_cows  =   get_bulls_and_cows( A, B );
 
    std::cout   <<  bulls_and_cows.first
                <<  " "
                <<  bulls_and_cows.second
                <<  std::endl;
}
0
1 / 1 / 1
Регистрация: 05.02.2018
Сообщений: 4
07.03.2018, 13:53 9
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
#include <iostream>
using namespace std;
 
 
void main() {
    setlocale(0, "");
    int x, y;
    cin >> x >> y;
    int mas[4], mas1[4];
    for (int i = 0; i < 4; i++) {
        mas[i] = x % 10;
        mas1[i] = y % 10;
        x /= 10;
        y /= 10;
 
    }
    int bik = 0; int kor = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
            if (mas[i] == mas1[j] && i == j) bik++;
            else if (mas[i] == mas1[j]) kor++;
        }
    cout << " Быков = " << bik << endl;
    cout << " Коров = " << kor << endl;
    system("pause");
}
1
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
07.03.2018, 22:26 10
Не надо эту задачу делать через рекурсию.

И да, я таки не смог понять, что должен делать твой алгоритм (что ещё один минус к рекурсии, так как основное её преимущество — понятность).

Вообще, эта задача решается очень просто. Просто надо перебирать цифры в обоих числах и считать.
Так как числа маленькие, можно вообще забить на всякие оптимизации.

Это можно сделать так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
constexpr size_t N = 4; // Длина числа
....
// first, second - числа, которые анализируем
char digits_first[N]; // цифры первого числа
for (unsigned i = 0, val = first; i<N;++i, val /=10)
{
   digits[i] = val%10;
}
size_t cows = 0, bulls = 0;
for (unsigned a = first, b = second; a; a/=10, b/=10)
{
   if (a%10==b%10)
      ++bulls;
   else if (std::find(digits, digits+N, b%10)!=digits+N)
      ++cows;
}
// Дальше выводим cows и bulls
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.03.2018, 22:26

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Переполнение стека
Доброго времени суток, форумчане! Начинаю плюсы осваивать, подскажите, безопасен ли код: ...

Переполнение стека
Всем привет. Помогите, пожалуйста с решением одной проблемы. Мне нужно в программе обрабатывать...

Рекурсия - переполнение стека
Помогите написать,задание ниже#include &quot;stdafx.h&quot; #include &quot;stdafx.h&quot; #include &lt;stdio.h&gt;...

Реализовать переполнение стека
Помогите пожалуйста: Задали написать программу, где будет переполнение стека ( если съедает...


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

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

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