Быки и коровы

@Даня98 · Регистрация: 13.02.2010

Студворк — интернет-сервис помощи студентам

Есть такая задача быки о коровы. Условие: http://acmp.ru/?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;
}

Но оно неправильно выдает кол-во коров. Т.к. я изучаю Си++ всего несколько недель, не могли бы Вы помочь найти здесь ошибку?

@don khuan · 10.08.2011, 16:23

Количество быков тоже неправильно выдает. все потому что во время выполнения цикла

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 · 10.08.2011, 16:56

строки сдесь не нужны

решение

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 · 10.08.2011, 16:58 **[ТС]**

Сообщение от Maxwe11

строки сдесь не нужны

Я не просил решение ибо мне надо понять свою ошибку.

Jupiter · 10.08.2011, 17:05

Сообщение от Даня98

мне надо понять свою ошибку.

тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи

Добавлено через 1 минуту

Сообщение от Даня98

C++
1
for (int i=0; i<5; i++)

так как нумерация массивов с нуля, то правильным условием завершения цикла должно быть i < 4

@Даня98 · 10.08.2011, 17:08 **[ТС]**

Сообщение от Maxwe11

тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи

Решение я расписал, быков переделаю но можете сказать как правильно сделать поиск коров со строками (не обращая внимания на быков). Как я уже говорил, Си++ я изучаю несколько недель и просто несколько сомневаюсь в коде а не псевдокоде на бумаге.

@talis · 10.08.2011, 17:42

Даня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_ · 10.08.2011, 19:02

Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма 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 · 10.08.2011, 19:20

Сообщение от Olga_

Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):

Позвольте с вами не согласится =)
В настолько детской задаче не имеет значения сложность алгоритма, даже при O(n^2), получается O(16)...
Гораздо важнее случайно не допустить где-нибудь ошибку(я про условия настоящей олимпиады, ну или если не стоит цель попасть в лучшие попытки, как у меня =) ).
А с использованием контейнеров и алгоритмов STL ошибку допустить очень сложно.
Но есть специальные задачи, в которых важна именно оптимальность алгоритма. Порешайте задачи из темы "Динамическое программирование" на acmp, вам понравится =)

@talis · 10.08.2011, 19:25

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_ · 10.08.2011, 19:28

Сообщение от diagon

Позвольте с вами не согласится...

Да вы правы, правы, Diagon, 100 раз правы, глупо было залезть в детскую тему. Пусть это будет как вариант, кто-то подумает, проанализирует, может понравится

Добавлено через 2 минуты

Сообщение от talis

Olga_, действительно, ваш алгоритм лучше. Если уж идти в сторону оптимизации, то можно отказаться от хранения чисел 0-9 в четырёх байтах int и хранить их в char, и выставлять 10 флагов не как 10 int по 4 байта каждый, а как 10 бит (в пределах двух байт).

И вы правы

С битами очень удобно

@Даня98 · 10.08.2011, 22:42 **[ТС]**

Сообщение от Olga_

Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):

У Вас не правильный алгоритм: введите 1234 1234 должно вывести 4 0, а у вас выводит 1 3.

Алгоритм O(N^2) работает правильнее чем O(N)

@Olga_ · 11.08.2011, 08:05

Сообщение от Даня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. Зачем народ баламутить

Новые блоги и статьи Все статьи Все блоги /
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 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .