Сапер: теория и практика Опции

[Vinchkovsky]

Здравствуйте
В общем, пишу сапер на Паскале, исключительно сам (впрочем, до этого момента), "от нечего делать", с псевдографикой и без использования приемов ООП.
Возникли два вопроса совершенно разного рода.

1) На поле есть такая ситуация (создавал в Paint, правя другое расположение мин, так что если есть какие-то несоответствия - извиняйте. Отдельное извинение за качество, случайно сохранил в .джпг, что мог - то подправил. Ну и английский ):


Допустим, все клетки поля не раскрыты. После нажатия клетки, которая "в фокусе" (выделенная зеленым), как должны открыться клетки? У меня варианта три:

Склоняюсь в верхнему справа, а что думаете вы?

2) Как можно гибко менять размеры окна (не в полноэкранном режиме)? Как я понял, с помощью процедуры TextMode гибкости не получить, я прав?

Спасибо

Сообщение отредактировано: volvo - 18.02.2009 23:03

[Lapp]

как генерируется поле?

Спасибо за вопрос, Clerick! Я как-то раньше не задумывался - плевал, пока не заплюю, с проверкой на повторы.. Но это же жутко неэффективно! Вот, задумался - результат тут:

const
  n=10;

var
  a: array[1..n]of integer;
  i,k: integer;

begin
  WriteLn('Total cells:  n=',n);
  Write('Type in number of cells to fill in (k<=n):  k=');
  ReadLn(k);
  Randomize;
  for i:=1 to n do if Random <= k/(n-i+1) then begin
    a[i]:=1;
    Dec(k)
  end
  else a[i]:=0;
  for i:=1 to n do Write(a[i]);
  ReadLn
end.

Алгоритм совсем простой - все заполняется за один проход )). И его легко распространить на двумерные массивы. Если что неясно - всегда к вашим услугам, как грится

[andriano]

Спасибо за вопрос, Clerick! Я как-то раньше не задумывался - плевал, пока не заплюю, с проверкой на повторы.. Но это же жутко неэффективно! Вот, задумался - результат тут...:

Есть такая статья, "Оптимизация – ваш злейший враг" http://www.rsdn.ru/article/philosophy/Optimization.xml
Там речь немного о другом, но заголовок идеально подходит к данному случаю.
В любом случае, если уж мы хотим оптимизировать, то должны сперва разобраться, а где же у нас узкое место.
В даном случае, очевидно, наиболее ресурсоемкой операцией является получение очередного ПСЧ. Да и весь цикл повторяется столько раз, сколько ячеек в поле.
По всей видимости, данный алгоритм должен заменить тот, в котором "метки" случайно набрасываются в поле с проверкой, не занята ли она уже.
Оцеки показывают, что количество проходов цикла и, соответственно, количество обращений к ДПСЧ будет меньше именно в исходном варианте при проценте заполнения не превосходящем примерно 60-67% (точно считать лень), т.е. алгоритм, предлагаемый как более эффективный, на самом деле имеет существенно меньшую эффективность. По краней мере, в большинстве случаев, когда процент заполнения менее упомянутых 60-67%. Если же процент заполнения больше, то задачу можно "перевернуть" и выбрасывать при помощи ДПСЧ "непомеченные" ячейки.
Таким образом, исходный алгоритм в слегка откорректированном виде будет ВСЕГДА эфективнее предложенного.

Пойдем дальше.
Можно ведт придумать алгоритм, в котором вызовов ДПСЧ будет РОВНО столько, сколько нужно помеченных клеток - и ни одной больше.
Навскидку могу предложить следующий (правда, не проверял его на качество распределения):
Нужно пометить K клеток из N, K < N.
1. В массиве заполняем первые K клеток, а остальные N-K оставляем пустыми.
2. Проходим циклом по первым K клеткам, для каждой находим случайное число в интервале [1..N] и обмениваем содержимое текущей [i] ячейки и ячейки с номером, соответствубщим выпавшему ПСЧ (для определенности - массив нумеруется с 1).

[Lapp]

Да, согласен. И идея обращения тоже хороша.
Но я хотел подправить свой вариант, и все же это сделаю - а то, он, ко все му прочему, еще и не надежный в таком виде). Так лучше:

const
  n=10;

var
  a: array[1..n]of integer;
  i,k: integer;

begin
  WriteLn('Total cells:  n=',n);
  Write('Type in number of cells to fill in (k<=n):  k=');
  ReadLn(k);
  Randomize;
  for i:=1 to n do if Random(n-i+1)<=k-1 then begin
    a[i]:=1;
    Dec(k)
  end
  else a[i]:=0;
  for i:=1 to n do Write(a[i]);
  ReadLn
end.