быки и коровы

[pif]

помогите найти оптимальный алгоритм решения игры "Быки и коровы", ну те алгоритм Кнута, и его программную реализацию, можно просто программу не обязательно код, но лучше с кодом.

[Veselyn]

#include <conio.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <time.h>

bool is_valid(char a[4],int size,char c)
{
	int no=size;
	for (int i=0;i<size;i++)
		if (a[i]!=c)
			no--;
	if (!no)
		a[size]=c;
	return !no;
}
int main(int argc, char* argv[])
{
	char my[4];
	int b,k,digits=0;
	char numbers[11]="0123456789";
	srand( (unsigned)time( NULL ) );
	while (digits<4)
		if (is_valid(my,digits,numbers[rand()%10]))
			digits++;
	//printf("my number is %c%c%c%c\n",my[0],my[1],my[2],my[3]);
	char enter[4],c(' ');
	b=k=digits=0;
	printf("Enter four digits or q for quit\n");
	while (c != 'q' && c != 'Q')
		if (isdigit(c=_getch()))
			if (is_valid(enter,digits,c))
			{
				printf("%c",c);
				for (int i=0;i<4;i++)
					if (my[i]==c)
						if (i==digits)
							b++;
						else
							k++;
				digits++;
				if (digits==4)
				{
					printf("\t\tb=%d k=%d\n",b,k);
					if (b==4){
						printf("U WON!");
						break;
					}
					b=k=digits=0;
				}
			}
	printf("\npress any key\n");
	_getch();
	return 0;
}

http://forum.sources.ru/index.php?showtopic=125340

[Somebody]

2 Veselyn: вроде как надо, чтобы прога отгадывала, а не юзер.
Кнута он или нет, не знаю, но суть такая: сначала считаем подходящими все правильные числа; спрашиваем про какое-нибудь число и, исходя из ответа, убираем из рассмотрения числа, на которые ответ был бы другим, так до тех пор, пока не угадаем.

#include <iostream>
#include <cstring>
#include <limits>

using namespace std;

void Split(int x, int& a, int& b, int& c, int& d)
{
	d = x % 10; x /= 10;
	c = x % 10; x /= 10;
	b = x % 10; x /= 10;
	a = x % 10;
}

bool IsValid(int x)
{
	int a, b, c, d;
	Split(x, a, b, c, d);
	return
		(a >= 1) && (a <= 9) &&
		(a != b) && (a != c) && (a != d) && (b != c) && (b != d) && (c != d);
}

bool Matches(int n1, int n2, int bulls, int cows)
{
	int a1, b1, c1, d1, a2, b2, c2, d2;
	Split(n1, a1, b1, c1, d1);
	Split(n2, a2, b2, c2, d2);
	return
		bulls == (
			(a1 == a2) + (b1 == b2) + (c1 == c2) + (d1 == d2)
		) &&
		cows == (
			(a1 == b2) + (a1 == c2) + (a1 == d2) +
			(b1 == a2) + (b1 == c2) + (b1 == d2) +
			(c1 == a2) + (c1 == b2) + (c1 == d2) +
			(d1 == a2) + (d1 == b2) + (d1 == c2)
		);
}

const int setSize = 10000;
bool badNum[setSize];

int main()
{
	memset(badNum, 0, sizeof(badNum));
	for (int i = 0; i < setSize; i++)
		badNum[i] = !IsValid(i);
	while (true)
	{
		int bulls, cows;
		int question;
		for (question = 0; question < setSize && badNum[question]; question++);
		if (question >= setSize)
		{
			cout << "bye 8-|";
			break;
		}
		cout << question << " ???" << endl;
		cout << "bulls, cows: ";
		cin >> bulls >> cows;
		if (bulls == 4 && cows == 0)
		{
			cout << "that's it :-)";
			break;
		}
		for (int i = 0; i < setSize; i++)
			badNum[i] = badNum[i] || !Matches(i, question, bulls, cows);
	}
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

[ddwrt]

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

2 Veselyn: вроде как надо, чтобы прога отгадывала, а не юзер.
Кнута он или нет, не знаю, но суть такая: сначала считаем подходящими все правильные числа; спрашиваем про какое-нибудь число и, исходя из ответа, убираем из рассмотрения числа, на которые ответ был бы другим, так до тех пор, пока не угадаем.

#include <iostream>
#include <cstring>
#include <limits>

using namespace std;

void Split(int x, int& a, int& b, int& c, int& d)
{
	d = x % 10; x /= 10;
	c = x % 10; x /= 10;
	b = x % 10; x /= 10;
	a = x % 10;
}

bool IsValid(int x)
{
	int a, b, c, d;
	Split(x, a, b, c, d);
	return
		(a >= 1) && (a <= 9) &&
		(a != b) && (a != c) && (a != d) && (b != c) && (b != d) && (c != d);
}

bool Matches(int n1, int n2, int bulls, int cows)
{
	int a1, b1, c1, d1, a2, b2, c2, d2;
	Split(n1, a1, b1, c1, d1);
	Split(n2, a2, b2, c2, d2);
	return
		bulls == (
			(a1 == a2) + (b1 == b2) + (c1 == c2) + (d1 == d2)
		) &&
		cows == (
			(a1 == b2) + (a1 == c2) + (a1 == d2) +
			(b1 == a2) + (b1 == c2) + (b1 == d2) +
			(c1 == a2) + (c1 == b2) + (c1 == d2) +
			(d1 == a2) + (d1 == b2) + (d1 == c2)
		);
}

const int setSize = 10000;
bool badNum[setSize];

int main()
{
	memset(badNum, 0, sizeof(badNum));
	for (int i = 0; i < setSize; i++)
		badNum[i] = !IsValid(i);
	while (true)
	{
		int bulls, cows;
		int question;
		for (question = 0; question < setSize && badNum[question]; question++);
		if (question >= setSize)
		{
			cout << "bye 8-|";
			break;
		}
		cout << question << " ???" << endl;
		cout << "bulls, cows: ";
		cin >> bulls >> cows;
		if (bulls == 4 && cows == 0)
		{
			cout << "that's it :-)";
			break;
		}
		for (int i = 0; i < setSize; i++)
			badNum[i] = badNum[i] || !Matches(i, question, bulls, cows);
	}
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

извините пожалуйста, а вы не подскажете, что делает функция Split?

[Izobara]

Общий алгоритм выглядит так (нам ведь отвечают больше-меньше, я помню):
Вначале берем средину числа (если 100, то берем 50). В зависимости от ответа отсекаем ненужную половину, а от оставшейся берем опять середину (51-100 - берем 75)... И дальше по фрактальной зависимости.

[ddwrt]

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

Общий алгоритм выглядит так (нам ведь отвечают больше-меньше, я помню):
Вначале берем средину числа (если 100, то берем 50). В зависимости от ответа отсекаем ненужную половину, а от оставшейся берем опять середину (51-100 - берем 75)... И дальше по фрактальной зависимости.

все равно немного не понял, мы же берем остаток от деления, а потом еще и делим на 10?

[Somebody]

Split просто разбивает число [abcd] на цифры.

[ddwrt]

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

Split просто разбивает число [abcd] на цифры.

Благодарю!