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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.87
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
#1

Быки и коровы - C++

10.08.2011, 16:05. Просмотров 5253. Ответов 12
Метки нет (Все метки)

Есть такая задача быки о коровы. Условие: http://********/?main=task&id_task=13. Код моего решения:
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
#include <fstream>
#include <string>
int main()
{
    std:: string t,f;
    int buki=0, korovy=0;
    std:: fstream ifs ("input.txt");
    ifs >> t >> f;   //чтение из файла
    ifs.close();
    
    for (int i=0; i<5; i++)
    if (t[i]==f[i])  //кол-во быков
    {
       buki++;
       f.erase (i-1,1);
    }
    for (int i=0;i<f.size(); i++)     //кол-во коров
    if (t.find(f[i])!=-1) korovy++;
    
    std:: ofstream ofs ("output.txt");
    ofs << buki << " " << korovy; //вывод
    ofs.close();
    return 0;
}
Но оно неправильно выдает кол-во коров. Т.к. я изучаю Си++ всего несколько недель, не могли бы Вы помочь найти здесь ошибку?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2011, 16:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быки и коровы (C++):

Быки и коровы - C++
Решил написать игру Быки и коровы, но уже в самом начале появились проблемы. я сделал функцию, которая считает количество быков, т.е....

Быки и коровы - C++
1. В чём разница между структурой и классом, зачем использовать структуру? 2. Зачем нужны структуры pair и four? 3. Что такое inline и...

Игра быки и коровы - C++
Условия игры: компьютер генерирует целое четырехзначное число, в котором все цифры раз-личны. Играющий пытается угадать это число, делая...

Игра: Быки и Коровы - C++
Всем привет! Нужно написать игру &quot;Быки и коровы&quot;, но без массива :) Я справился с поставленной задачей, но есть баг... Если компьютер...

Быки и коровы. Комментарии к коду. - C++
Нужно прокомментировать программу на языке с++ Игра Быки и Коровы. Чем подробнее тем лучше. Заранее спасибо! #include &quot;stdafx.h&quot; ...

Быки и коровы, не правильно считает их - C++
Не правильно считает быков и коров, помогите пожалуйста #include &lt;iostream&gt; #include &lt;locale.h&gt; #include &lt;cstdlib&gt; // rand() ...

12
don khuan
2 / 2 / 0
Регистрация: 02.08.2011
Сообщений: 22
10.08.2011, 16:23 #2
Количество быков тоже неправильно выдает. все потому что во время выполнения цикла
C++
1
2
3
4
5
6
    for (int i=0; i<5; i++)
    if (t[i]==f[i])  //кол-во быков
    {
       buki++;
       f.erase (i-1,1);
    }
если бык найден, то удаляется символ из строки f, смещаются индексы и получается так, что к концу цикла в f не хватает элементов

как вариант - убрать удаление и в поиске коров добавить условие t[i]!=f[i]
1
Jupiter
Каратель
Эксперт С++
6556 / 3977 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
10.08.2011, 16:56 #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
#include <fstream>
 
int main()
{
    unsigned petya, vasya;
    std::fstream ifs("input.txt");
    std::ofstream ofs("output.txt");
    ifs >> petya >> vasya;   //чтение из файла
 
    unsigned peet[4], vas[4];
    for (unsigned i = 0; i < 4; ++i, petya /= 10, vasya /= 10)
    {
        peet[4-i-1] = petya % 10;
        vas[4-i-1]  = vasya % 10;
    }
 
    unsigned bulls(0), cows(0);
    for (unsigned i = 0; i < 4; ++i)
    {
        for (unsigned j = 0; j < 4; ++j)
        {
            if (peet[i] == vas[j])
            {
                if (i == j)
                    ++bulls;
                else
                    ++cows;
            }
        }
    }
 
    ofs << bulls << ' ' << cows;
    return 0;
}
1
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 16:58  [ТС] #4
Цитата Сообщение от Maxwe11 Посмотреть сообщение
строки сдесь не нужны
Я не просил решение ибо мне надо понять свою ошибку.
0
Jupiter
Каратель
Эксперт С++
6556 / 3977 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
10.08.2011, 17:05 #5
Цитата Сообщение от Даня98 Посмотреть сообщение
мне надо понять свою ошибку.
тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи

Добавлено через 1 минуту
Цитата Сообщение от Даня98 Посмотреть сообщение
C++
1
for (int i=0; i<5; i++)
так как нумерация массивов с нуля, то правильным условием завершения цикла должно быть i < 4
0
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 17:08  [ТС] #6
Цитата Сообщение от Maxwe11 Посмотреть сообщение
тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи
Решение я расписал, быков переделаю но можете сказать как правильно сделать поиск коров со строками (не обращая внимания на быков). Как я уже говорил, Си++ я изучаю несколько недель и просто несколько сомневаюсь в коде а не псевдокоде на бумаге.
0
talis
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
10.08.2011, 17:42 #7
Даня98, можно в двух циклах. В первом проходите первую группу символов, во втором вторую. Во втором цикле поверяете: если символы равны и стоят на одинаковой позиции, инкрементируете счётчик быков, если же символы равны, но стоят на разных позициях, то инкрементируете счётчик коров.

Посмотреть код

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
//#include <iostream> // для cerr
#include <fstream>
 
using namespace std;
 
int main()
{
    ifstream in  ( "input.txt" );
    ofstream out ( "output.txt" );
 
    char instr[10];
 
    in.get( instr, 10 );
 
    // опционально ------------------------
    //if( instr[4] != ' ' || instr[9] != 0 )
    //{
    //   cerr << "wrong format" << endl;
    //   return -1;
    //}
    // -------------------------------------
 
    char bulls = 0, cows = 0;
 
    for( char i = 0; i < 4; i++ )
    {
        for( char u = 5; u < 9; u++ )
        {
            if( instr[i] == instr[u] )
            {
                if( i == u - 5 )
                   bulls++;
                else
                   cows++;
            }
        }
    }
 
    out << (int)bulls << ' ' << (int)cows;
 
    return 0;
}


Таким образом за один раз находите и всех быков, и всех коров.

Добавлено через 2 минуты
Можно ещё больше сэкономить, если сделать на C


Добавлено через 6 минут
На C
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
#include <stdio.h>
 
int main()
{
    FILE * in = fopen( "input.txt", "r" );
    FILE * out = fopen ( "output.txt", "w" );
 
    if( !in || !out )
       return -1;
 
    char instr[10];
 
    fread( instr, 1, 10, in );
 
    unsigned char bulls = 0, cows = 0, i = 0, u;
 
    for( ; i < 4; i++ )
    {
        for( u = 5; u < 9; u++ )
        {
            if( instr[i] == instr[u] )
            {
                if( i == u - 5 )
                   bulls++;
                else
                   cows++;
            }
        }
    }
 
    instr[0] = bulls + 0x30;
    instr[1] = ' ';
    instr[2] = cows + 0x30;
 
    fwrite( instr, 1, 3, out );
 
    fclose( in );
    fclose( out );
 
    return 0;
}
1
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 19:02 #8
Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):


C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Count(int *x, int *y, int n, int *bull, int *cow)
{
   int i, flag[10] = {0};
   *bull = *cow = 0;
   for (i = 0; i < n; i++)
      if (x[i] == y[i])
         (*bull)++;
      else
         flag[x[i]] = 1;
   for (i = 0; i < n; i++)
      if (flag[y[i]])
         (*cow)++;
}
 
int main()
{
   int x[4] = {1,2,3,4}, y[4] = {2,5,3,1};
   int bull, cow;
   Count(x, y, 4, &bull, &cow);
   printf("bull = %d cow = %d\n", bull, cow);
   return 0;
}
2
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 19:20 #9
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Olga_ Посмотреть сообщение
Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):
Позвольте с вами не согласится =)
В настолько детской задаче не имеет значения сложность алгоритма, даже при O(n^2), получается O(16)...
Гораздо важнее случайно не допустить где-нибудь ошибку(я про условия настоящей олимпиады, ну или если не стоит цель попасть в лучшие попытки, как у меня =) ).
А с использованием контейнеров и алгоритмов STL ошибку допустить очень сложно.
Но есть специальные задачи, в которых важна именно оптимальность алгоритма. Порешайте задачи из темы "Динамическое программирование" на acmp, вам понравится =)
3
talis
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
10.08.2011, 19:25 #10
Olga_, действительно, ваш алгоритм лучше. Если уж идти в сторону оптимизации, то можно отказаться от хранения чисел 0-9 в четырёх байтах int и хранить их в char, и выставлять 10 флагов не как 10 int по 4 байта каждый, а как 10 бит (в пределах двух байт). Уйму памяти сэкономим...

Оптимизируем дальше

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
void Count(char *x, char *y, char n, char *bull, char *cow)
{
   char i;
   unsigned short flag = 0;
 
   *bull = *cow = 0;
 
   for ( i = 0; i < n; i++ )
   {
      if ( x[i] == y[i] )
         (*bull)++;
      else
         flag |= 1 << x[i];
   }
 
 
   for ( i = 0; i < n; i++ )
   {
      if ( flag & 1 << y[i] )
         (*cow)++;
   }
}
 
int main()
{
   char x[4] = { 0,2,3,4 },
        y[4] = { 1,8,6,3 };
 
   char bull, cow;
 
   Count( x, y, 4, &bull, &cow );
 
   printf( "bull = %d cow = %d\n", bull, cow );
   return 0;
}


Так же для ликвидации накладных расходов на вызов функции, можно и от неё отказаться :-)
2
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 19:28 #11
Цитата Сообщение от diagon Посмотреть сообщение
Позвольте с вами не согласится...
Да вы правы, правы, Diagon, 100 раз правы, глупо было залезть в детскую тему. Пусть это будет как вариант, кто-то подумает, проанализирует, может понравится

Добавлено через 2 минуты
Цитата Сообщение от talis Посмотреть сообщение
Olga_, действительно, ваш алгоритм лучше. Если уж идти в сторону оптимизации, то можно отказаться от хранения чисел 0-9 в четырёх байтах int и хранить их в char, и выставлять 10 флагов не как 10 int по 4 байта каждый, а как 10 бит (в пределах двух байт).
И вы правы С битами очень удобно
1
Даня98
28 / 28 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 22:42  [ТС] #12
Цитата Сообщение от Olga_ Посмотреть сообщение
Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):
У Вас не правильный алгоритм: введите 1234 1234 должно вывести 4 0, а у вас выводит 1 3.

Алгоритм O(N^2) работает правильнее чем O(N)
1
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 08:05 #13
Цитата Сообщение от Даня98 Посмотреть сообщение
У Вас не правильный алгоритм: введите 1234 1234 должно вывести 4 0, а у вас выводит 1 3.

Алгоритм O(N^2) работает правильнее чем O(N)
Даня98, вы как проверяли? Проверьте еще раз

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Count(int *x, int *y, int n, int *bull, int *cow)
{
   int i, flag[10] = {0};
   *bull = *cow = 0;
   for (i = 0; i < n; i++)
      if (x[i] == y[i])
         (*bull)++;
      else
         flag[x[i]] = 1;
   for (i = 0; i < n; i++)
      if (flag[y[i]])
         (*cow)++;
}
 
int main()
{
   int x[4] = {1,2,3,4}, y[4] = {1,2,3,4};
   int bull, cow;
   Count(x, y, 4, &bull, &cow);
   printf("bull = %d cow = %d\n", bull, cow);
   getchar();
   return 0;
}
Ответ выводит bull = 4, cow = 0. Зачем народ баламутить
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 08:05
Привет! Вот еще темы с ответами:

Задача про вектор для игры "Быки и коровы" - C++
Задача из книги Страуструпа, вот условие : программа должна хранить вектор из четырех различных чисел в диапазоне от 0 до 9 (т.е.,...

Ошибка в коде игры "Быки и коровы" - C++
#include &lt;iostream&gt; #include &quot;Game.h&quot; using namespace std; Game::Game() { com; per; } Game:: ~Game() { delete per; ...

Функция для игры "быки и коровы" - C++
Помогите составить код для С++, для раздела Функции. сама задача Компьютер задумывает четырехзначное число, не содержащее двух...

Алгоритм игры "Быки и коровы" - C++
Игра &quot;Быки и коровы&quot;. Вы загадываете пятизначное число. Программа дает Вам другое четырехзначное число. Вы отвечаете, сколько цифр в числах...


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

Или воспользуйтесь поиском по форуму:
13
Yandex
Объявления
11.08.2011, 08:05
Ответ Создать тему
Опции темы

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