Получить последовательность a1…an цифр 0,1,2, в которой нет смежных одинаковых участков

18 мая 2009

Программа должна генерировать последовательность любой длины из цифр 0, 1 и 2, но она не должна содержать в себе одинаковых участков таких как, например, последовательность 1010 – недопустимо, т.к. участки 10 и 10 расположены один за другим; последовательность 120120 – имеются два одинаковых участка 120 и 120.

Напишем функцию “check_str”, которая будет возвращать “false” в случае если найден одинаковый участок в последовательности “s”.

Boolean check_str(string s) {
	string start, end;
	for (int i = 1; i < = s.Length / 2; i++) {
		start = s.Substring(0, s.Length - i);
		end = s.Substring(s.Length - i, i);
		
		if (start.Length < end.Length)
			return true;
			
		if (start.Substring(start.Length - i, i) == end)
			return false;
	}
	return true;
}

В функции выполняется проверка на все возможные смежные одинаковые участки. Разберем работу функции на примере последовательности 120120. Для выполнения всех проверок достаточно всего 3 прохода, при первом проходе сравниваются последние цифры 120120, если они равны, то одинаковый участок найден и выполняется завершение работы функции, в противном случае выполняется 2-й проход и уже сравниваются цифры 01 и 20. При следующем и последнем проходе сравниваются первые и последние 3 цифры 120 и 120, вот теперь они равны и производится выход из функции, возвращается значение “false”.
Теперь рассмотрим код процедуры “generate_Click”, которая вызывается при нажатии на кнопку “generate”.

private void generate_Click(object sender, EventArgs e) {
	int kol = Convert.ToInt32(kolvo.Text);
	Random r = new Random();
	generate_num.Clear();
	int x;
	string s = "";
	for (int i = 1; i < = kol; i++)	{
		for (; ; ) {
			x = r.Next(0, 3);
			if (i == 1)	{
				s = Convert.ToString(x);
				break;
			}
			if (check_str(s + Convert.ToString(x)))	{
				s += Convert.ToString(x);
				break;
			}
			else {
				if (!check_str(s + "0") && !check_str(s + "1") && !check_str(s + "2")) {
					generate_num.Text = s + " (Дальнейшая генерация числа невозможна)";
					return;
				}
			}
		}
	}
	generate_num.Text += s;
}

В этом процедуре происходит автоматическая генерация цифр от 0 до 2, добавление цифры к строке “s” (в случае положительного результата от функции “check_str”) и вывод сгенерированной последовательности на форму пользователя.
Бывают такие случаи, когда невозможна дальнейшая генерации последовательности, в этом случае выводится последовательность и текст “(Дальнейшая генерация числа невозможна)”.

Автор: Евтеев Евгений Александрович