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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.87
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 16:05     Быки и коровы #1
Есть такая задача быки о коровы. Условие: 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;
}
Но оно неправильно выдает кол-во коров. Т.к. я изучаю Си++ всего несколько недель, не могли бы Вы помочь найти здесь ошибку?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2011, 16:05     Быки и коровы
Посмотрите здесь:

C++ [C++] подскажите Алгоритм игры "быки и коровы"
C++ Быки и коровы
C (СИ) Быки и коровы
Быки и коровы, не правильно считает их C++
Суточный рацион коровы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
don khuan
 Аватар для 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]
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 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;
}
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 16:58  [ТС]     Быки и коровы #4
Цитата Сообщение от Maxwe11 Посмотреть сообщение
строки сдесь не нужны
Я не просил решение ибо мне надо понять свою ошибку.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 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
Даня98
 Аватар для Даня98
27 / 27 / 8
Регистрация: 13.02.2010
Сообщений: 145
10.08.2011, 17:08  [ТС]     Быки и коровы #6
Цитата Сообщение от Maxwe11 Посмотреть сообщение
тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи
Решение я расписал, быков переделаю но можете сказать как правильно сделать поиск коров со строками (не обращая внимания на быков). Как я уже говорил, Си++ я изучаю несколько недель и просто несколько сомневаюсь в коде а не псевдокоде на бумаге.
talis
 Аватар для talis
789 / 541 / 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;
}
Olga_
 Аватар для Olga_
840 / 182 / 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;
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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, вам понравится =)
talis
 Аватар для talis
789 / 541 / 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;
}


Так же для ликвидации накладных расходов на вызов функции, можно и от неё отказаться :-)
Olga_
 Аватар для Olga_
840 / 182 / 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 бит (в пределах двух байт).
И вы правы С битами очень удобно
Даня98
 Аватар для Даня98
27 / 27 / 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)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 08:05     Быки и коровы
Еще ссылки по теме:

C++ Быки и коровы. Комментарии к коду.
C++ Игра быки и коровы
Быки и коровы C++

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

Или воспользуйтесь поиском по форуму:
Olga_
 Аватар для Olga_
840 / 182 / 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. Зачем народ баламутить
Yandex
Объявления
11.08.2011, 08:05     Быки и коровы
Ответ Создать тему
Опции темы

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