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

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

25.01.2016, 19:47. Показов 4086. Ответов 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
25.01.2016, 19:47
Ответы с готовыми решениями:

Переполнение стека
Хочу полюбопытствовать. Вычитал недавно, что на стек выделяется ограниченная область памяти, и в языке Си это 4 Кб. Вопрос: Если мне...

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

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

9
Native x86
Эксперт Hardware
 Аватар для quwy
6853 / 3787 / 1024
Регистрация: 13.02.2013
Сообщений: 11,861
25.01.2016, 19:49
Какая любопытная запись условия:
Code
1
while (-1 < z < 4)
Кто вас такому научил?
1
1 / 1 / 1
Регистрация: 02.12.2013
Сообщений: 30
25.01.2016, 19:51  [ТС]
Цитата Сообщение от quwy Посмотреть сообщение
Какая любопытная запись условия:
CodeВыделить код
1
while (-1 < z < 4)
Кто вас такому научил?
Да никто.
Таким образом я попытался реализовать условие, что подаётся на вход только четырёхзначное число. (ну и 4 ячейки массива выделены под это дело)
1
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
25.01.2016, 19:51
Цитата Сообщение от roman0412 Посмотреть сообщение
Можете помочь мне это исправить?
Избавься от локальных переменных внутри рекурсивных функций. Если не поможет - избавься от рекурсии. Если не поможет - ищи ошибку в посте №2.
1
Native x86
Эксперт Hardware
 Аватар для quwy
6853 / 3787 / 1024
Регистрация: 13.02.2013
Сообщений: 11,861
25.01.2016, 19:55
Цитата Сообщение от roman0412 Посмотреть сообщение
Таким образом я попытался реализовать условие, что подаётся на вход только четырёхзначное число. (ну и 4 ячейки массива выделины под это дело)
Это условие работает так: сначала вычисляется значение -1 < z, которое будет равно либо TRUE, либо FALSE в зависимости от значения z. А потом этот результат поступает как левая часть в выражение < 4. А т.к. FALSE приводится к 0, а TRUE соответственно к 1, условие получается всегда истинным (и 0 и 1 меньше 4), ваш цикл становится бесконечным, а значит и рекурсия становится бесконечной, в итоге переполнение стека.
2
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
25.01.2016, 20:02
Всё верно. Так условие не пишется.
Для условия -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  [ТС]
Цитата Сообщение от quwy Посмотреть сообщение
Это условие работает так: сначала вычисляется значение -1 < z, которое будет равно либо TRUE, либо FALSE в зависимости от значения z. А потом этот результат поступает как левая часть в выражение < 4. А т.к. FALSE приводится к 0, а TRUE соответственно к 1, условие получается всегда истинным (и 0 и 1 меньше 4), ваш цикл становится бесконечным, а значит и рекурсия становится бесконечной, в итоге переполнение стека.
Спасибо.
Я попробовал сделать так:
while (z > -1 && z < 4);
Мой новый метод тоже не сработал. (рекурсия никуда не делась) Можете объяснить почему?
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2016, 22:04
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
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
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
07.03.2018, 22:26
Не надо эту задачу делать через рекурсию.

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

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

Это можно сделать так:
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
07.03.2018, 22:26
Помогаю со студенческими работами здесь

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

Переполнение стека
Доброго времени суток, форумчане! Начинаю плюсы осваивать, подскажите, безопасен ли код: #include &lt;stdio.h&gt; int main(int...

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

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

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Ниже машинный перевод статьи The Thinkpad X220 Tablet is the best budget school laptop period . Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы,. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru