powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обход прямоугольника по спирали. Поиск более подходящего алгоритма
88 сообщений из 88, показаны все 4 страниц
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38765570
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте. Решал сегодня достаточно простую задачу, но решил её не оптимально. Привожу ссылку на саму задачу .

Вот как я её решаю

Код: plaintext
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.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
#include <stdio.h>
#include <stdlib.h>

/*
 *На входе спираль в двумерном массиве(spiral,m,n), указатели на текущее положение в спирали(i,j),
 *статус движения с пирали: 0-вправо,1-вниз,2-влево,3-вверх
 *Функция изменяет значения текущего положения в спирали(i,j), 
 *при необходимости изменяется статус движения. Устанавливает уже пройденные значения в 1.
 *При успешном завершении функции возвращается 0.
 */
int move_on_square_spiral(int* s, int n, int m, int* cur_i, int* cur_j, int* cur_state)
{
	int i = *cur_i;
	int j = *cur_j;
	int state = *cur_state % 4;

	if (state == 0) //вправо
	{
		if (j < m-1 && s[i*m + j + 1]!= 1)
		{
			s[i*m + j + 1] = 1;
			*cur_j += 1;
		}
		else
		{
			s[(i + 1)*m + j]=1;
			*cur_i += 1;
			*cur_state += 1;
		}
	}
	else if (state==1)//вниз
	{
		if (i < n-1 && s[(i+1)*m+j] != 1)
		{
			s[(i + 1)*m + j]=1;
			*cur_i += 1;
		}
		else
		{
			s[i*m + j-1] = 1;
			*cur_j -= 1;
			*cur_state += 1;
		}
	}
	else if (state == 2)//влево
	{
		if (j > 0 && s[i*m+j-1] != 1)
		{
			s[i*m + j - 1] = 1;
			*cur_j -= 1;
		}
		else
		{
			s[(i - 1)*m + j] = 1;
			*cur_i -= 1;
			*cur_state += 1;
		}
	}
	else if (state == 3)//вверх
	{
		if (i > 0 && s[(i-1)*m+j] != 1)
		{
			s[(i - 1)*m + j] = 1;
			*cur_i -= 1;
		}
		else
		{
			s[i*m + j+1] = 1;
			*cur_j += 1;
			*cur_state += 1;
		}
	}
	return 0;
}

int main(int argc, char** argv)
{
	FILE* in = fopen("input.txt", "r");
	if (!in)
	{
		printf("File 'input.txt' not found.\n");
		return 0;
	}

	//чтение и запись входных параметров
	int n, m;
	int end_i, end_j;
	fscanf(in, "%i %i", &n, &m);
	fscanf(in, "%i %i", &end_i, &end_j);
	fclose(in);

	end_i -= 1;
	end_j -= 1;

	//инициализация спирали
	int* a = (int*)calloc(n*m, sizeof(int));
	a[0] = 1;

	//основная часть
	int res = 1;
	int cur_i = 0, cur_j = 0;
	int cur_state = 0;

	while (!(cur_i==end_i && cur_j==end_j))
	{
		move_on_square_spiral(a, n, m, &cur_i, &cur_j, &cur_state);
		res += 1;
	}

	FILE* out = fopen("output.txt", "w");
	fprintf(out, "%i", res);
	fclose(out);
	
	return 0;

}



Очевидно что алгоритм не оптимален. Мне в голову пришёл другой способ решения данной задачи,


Элементы суммы есть количество элементов прямоугольников окружающих прямоугольник содержащий нужную координату, дельта-сдвиг внутри прямоугольника содержащего нужный элемент. Мне кажется что данный алгоритм вполне можно реализовать. Так ли это ?

Приходят ли вам в голову ещё какие-либо способы решения данной задачи ?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38765571
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, мой код можно оптимизировать, только пока я не решил как, и стоит ли это делать.
Возможно вы реализовали бы по-другому уже реализованный алгоритм ?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38765572
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Память забыл освободить. Прошу прощение (это все после перелета((( ).
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38765694
andreymx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
помню, в 1990-ом писал змею в лабиринте
очень интересно было
:)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38765970
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryПамять забыл освободить. Прошу прощение (это все после перелета((( ).
Саш ты как всегда наколбасил тучу ненужного кода. У тебя в функции move_on_square_spiral
идёт сплошная копи-паста одного и того-же расчётного блока с небольшими изменениями вектора
движения который ты прибавляешь к cur_i, cur_j.

Не нужно быть Фаулером чтобы сказать что это код "смердит" и срочно требует рефакторингов.

Кстати почитай про Аффинные преобразования на плоскости и в частности
Поворот вектора на 90 градусов.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766176
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, спасибо :)
Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно.

Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766182
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymayton, спасибо :)
Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно.

Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ?
Конкретное? Вечером я допью чай. И как покромсаю твой сорц.
Ожидаю чуть более чем наполовину сокращение количества
ненужных символов.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766275
nolocky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymayton, спасибо :)
Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно.

Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ?

вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи.

когда вы уже отучитись от "стиля" их 70-х годов?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766321
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
nolockyвообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи.
По вашему... можно-ли взять за правило - переписывать любой I/O на mmap?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766583
nolocky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonnolockyвообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи.
По вашему... можно-ли взять за правило - переписывать любой I/O на mmap?

В современном мире - да. Есть только одна задача, где это не нужно делать - это syslog

Для сети же есть splice и sendfile, там тоже, внезапно, все вокруг mmap
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766771
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
nolockySashaMercurymayton, спасибо :)
Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно.

Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ?

вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи.

когда вы уже отучитись от "стиля" их 70-х годов?

Я уверен в том, что не вы определяете правила приличного общества
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766848
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

не отлаживал, тест прошла - и ладно )

Код: pascal
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.
function CellCount(M, N, X, Y: integer): integer;
var
  Top, Right, Bottom, Left, Direction, LoopCount: integer;
begin;
  Top:=Y-1; Right:=M-X; Bottom:=N-Y; Left:=X-1;
  LoopCount:=Top; DiRection:=0;
  if LoopCount>Right then begin; LoopCount:=Right; Direction:=1; end;
  if LoopCount>Bottom then begin; LoopCount:=Bottom; Direction:=2; end;
  if LoopCount>Left then begin; LoopCount:=Left; Direction:=3; end;
  Result:=0;
  if LoopCount>0 then Result:=2*(M+N-2*LoopCount)*LoopCount;
  if Direction=0 then Result:=Result+X-LoopCount
  else begin;
    Result:=Result+M-2*LoopCount-1;
    if Direction=1 then Result:=Result+Y-LoopCount
    else begin;
      Result:=Result+N-2*LoopCount-1;
      if Direction=2 then Result:=Result+M-LoopCount-X
      else begin;
        Result:=Result+M-2*LoopCount-1;
        Result:=Result+N-LoopCount-Y;
        end;
      end;
    end;
  end;

procedure TForm1.Button1Click(Sender: TObject);
begin;
  Memo1.Lines.Add(Format('%d %d %d %d %d',[1,1,1,1,CellCount(1,1,1,1)]));
  Memo1.Lines.Add(Format('%d %d %d %d %d',[3,3,2,3,CellCount(3,3,3,2)]));
  Memo1.Lines.Add(Format('%d %d %d %d %d',[5,5,2,3,CellCount(5,5,3,2)]));
  Memo1.Lines.Add(Format('%d %d %d %d %d',[5,5,3,3,CellCount(5,5,3,3)]));
  end;
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766849
nolocky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurynolockyпропущено...


вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи.

когда вы уже отучитись от "стиля" их 70-х годов?

Я уверен в том, что не вы определяете правила приличного общества

Конечно не я, разве я где-то говорил, что использовать mmap - это правило, придуманное лично мною?

Ты неудачно решил показаться умным. У тебя это не получилось.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766870
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

вкралась пара неточностей с обратным ходом, исправил
Код: pascal
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.
function CellCount1(M, N, X, Y: integer): integer;
var
  Top, Right, Bottom, Left, Direction, LoopCount: integer;
begin;
  Top:=Y-1; Right:=M-X; Bottom:=N-Y; Left:=X-1;
  LoopCount:=Top; DiRection:=0;
  if LoopCount>Right then begin; LoopCount:=Right; Direction:=1; end;
  if LoopCount>Bottom then begin; LoopCount:=Bottom; Direction:=2; end;
  if LoopCount>Left then begin; LoopCount:=Left; Direction:=3; end;
  Result:=0;
  if LoopCount>0 then Result:=2*(M+N-2*LoopCount)*LoopCount;
  if Direction=0 then Result:=Result+X-LoopCount
  else begin;
    Result:=Result+M-2*LoopCount-1;
    if Direction=1 then Result:=Result+Y-LoopCount
    else begin;
      Result:=Result+N-2*LoopCount-1;
      if Direction=2 then Result:=Result+M-LoopCount-X+1
      else begin;
        Result:=Result+M-2*LoopCount-1;
        Result:=Result+N-LoopCount-Y+1;
        end;
      end;
    end;
  end;



или эквивалентная версия через case
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
function CellCount2(M, N, X, Y: integer): integer;
var
  Top, Right, Bottom, Left, Direction, LoopCount: integer;
begin;
  Top:=Y-1; Right:=M-X; Bottom:=N-Y; Left:=X-1;
  LoopCount:=Top; DiRection:=0;
  if LoopCount>Right then begin; LoopCount:=Right; Direction:=1; end;
  if LoopCount>Bottom then begin; LoopCount:=Bottom; Direction:=2; end;
  if LoopCount>Left then begin; LoopCount:=Left; Direction:=3; end;
  Result:=0;
  if LoopCount>0 then Result:=2*(M+N-2*LoopCount)*LoopCount;
  case Direction of
    0: Result:=Result+X-LoopCount;
    1: Result:=Result+Y-3*LoopCount+M-1;
    2: Result:=Result-X-5*LoopCount+2*M+N-1;
    3: Result:=Result-Y-7*LoopCount+2*M+2*N-2;
    end;
  end;
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766895
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
nolockySashaMercuryпропущено...


Я уверен в том, что не вы определяете правила приличного общества

Конечно не я, разве я где-то говорил, что использовать mmap - это правило, придуманное лично мною?

Ты неудачно решил показаться умным. У тебя это не получилось.

Вы вообще адекватный человек ? В каком месте я решил показаться умным, тут половина форума умнее меня, и я это говорил всегда, и именно поэтому я обращаюсь к этому форуму за советом.
Администрация, уберите его отсюда, очевидно что этот идиот меня провоцирует. Хватает идиотов в жизни, я минимизировал свое появление в интернете только до этого сайта, и никак не ожидал встретить такого кретина тут.

Администрация, я ещё раз отмечаю, его сообщение выше очевидная провокация. Примите меры к этому пользователю.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766896
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr SharahovAleksandr Sharahov,

вкралась пара неточностей с обратным ходом, исправил
Код: pascal
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.
function CellCount1(M, N, X, Y: integer): integer;
var
  Top, Right, Bottom, Left, Direction, LoopCount: integer;
begin;
  Top:=Y-1; Right:=M-X; Bottom:=N-Y; Left:=X-1;
  LoopCount:=Top; DiRection:=0;
  if LoopCount>Right then begin; LoopCount:=Right; Direction:=1; end;
  if LoopCount>Bottom then begin; LoopCount:=Bottom; Direction:=2; end;
  if LoopCount>Left then begin; LoopCount:=Left; Direction:=3; end;
  Result:=0;
  if LoopCount>0 then Result:=2*(M+N-2*LoopCount)*LoopCount;
  if Direction=0 then Result:=Result+X-LoopCount
  else begin;
    Result:=Result+M-2*LoopCount-1;
    if Direction=1 then Result:=Result+Y-LoopCount
    else begin;
      Result:=Result+N-2*LoopCount-1;
      if Direction=2 then Result:=Result+M-LoopCount-X+1
      else begin;
        Result:=Result+M-2*LoopCount-1;
        Result:=Result+N-LoopCount-Y+1;
        end;
      end;
    end;
  end;



или эквивалентная версия через case
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
function CellCount2(M, N, X, Y: integer): integer;
var
  Top, Right, Bottom, Left, Direction, LoopCount: integer;
begin;
  Top:=Y-1; Right:=M-X; Bottom:=N-Y; Left:=X-1;
  LoopCount:=Top; DiRection:=0;
  if LoopCount>Right then begin; LoopCount:=Right; Direction:=1; end;
  if LoopCount>Bottom then begin; LoopCount:=Bottom; Direction:=2; end;
  if LoopCount>Left then begin; LoopCount:=Left; Direction:=3; end;
  Result:=0;
  if LoopCount>0 then Result:=2*(M+N-2*LoopCount)*LoopCount;
  case Direction of
    0: Result:=Result+X-LoopCount;
    1: Result:=Result+Y-3*LoopCount+M-1;
    2: Result:=Result-X-5*LoopCount+2*M+N-1;
    3: Result:=Result-Y-7*LoopCount+2*M+2*N-2;
    end;
  end;




Спасибо :) Скоро займусь вашей реализацией
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766900
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov, а можно услышать ваши комментарии по вашей реализации ?)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766909
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

вот это еще посмотрите:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function CellCount3(M, N, X, Y: integer): integer;
var
  T: integer;
begin;
  Result:=0;
  while Y<>1 do begin;
    Result:=Result+M;
    T:=Y-1; Y:=M-X+1; X:=T;
    T:=N-1; N:=M; M:=T;
    end;
  Result:=Result+X;
  end;
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766915
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryAleksandr Sharahov, а можно услышать ваши комментарии по вашей реализации ?)

CellCount1, CellCount2 в вычисляют количество клеток в полных обходах как разность площадей двух прямоугольников M*N и (M-2*LoopCount)*(N-2*LoopCount), а затем делают неполный проход по сторонам внутреннего прямоугольника.

CellCount3 в цикле срезает верхний слой прямоугольника и поворачивает прямоугольник на 90 до тех пор пока точка не окажется в этом слое, а затем прибавляет расстояние до нее.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766932
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Проверьте пожалуйста прямоугольник 10 3 , точка 5 2, и прямоугольник 100 000 100 000, точка 50000 50000
Сейчас сам не могу этого сделать, пишу не с того компьютера где это возможно, и меня уже заставляют его выключать(
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766939
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryПроверьте пожалуйста прямоугольник 10 3 , точка 5 2, и прямоугольник 100 000 100 000, точка 50000 50000
Сейчас сам не могу этого сделать, пишу не с того компьютера где это возможно, и меня уже заставляют его выключать(

26
1410065405
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38766981
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В данной задаче я проглядел одно важное условие - в каждой клетке растёт по ягоде.
Вобщем уравнение движения Медведя в динамике никому не нужно. Мы заранее
знаем сколько он соберёт ягод исходя геометрии на плоскости.

Формула упрощается до разности площадей двух прямоугольников.

Последний (финальный) круг медведя решается требует двух-трех проверок
условий и коррекции площади.

Циклы и рекурсии для решения данной задачи не нужны.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767046
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а это комбинация идей из CellCount1 и CellCount3:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
function CellCount4(M, N, X, Y: integer): integer;
var
  I, T, Z, R: integer;
begin;
  Result:=0; Z:=0; R:=0;
  for I:=0 to 3 do begin;
    if (I=0) or (Z>=Y) then begin;
      Z:=Y-1;
      Result:=2*Z*(M+N-2*Z)+X-Z*(I*2+1)+R;
      end;
    R:=R+M-1;
    T:=Y; Y:=M-X+1; X:=T;
    T:=N; N:=M; M:=T;
    end;
  end;
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767074
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
nolockySashaMercurymayton, спасибо :)
Не уверен что прочитаю что-то новое из того что вы предложили. По поводу рефакторинга согласен, но не уверен. Займусь им обязательно.

Меня интересуют другие методы или реализации. Вы можете предложить что-нибудь более конкретное ?

вообще-то в приличном обществе приходить с fscanf/fprintf не принято - есть же mmap, господи.

когда вы уже отучитись от "стиля" их 70-х годов?


нахрена mmap?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767079
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
без этой хрени получаются хреновые алгоритмы)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767080
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
без этой хрени получаются хреновые алгоритмы)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767120
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У меня такой вопрос. Я дал вам площадку 10^6 на 10^6.
Общая площадь 10^12, это примерно 3.2*12 бит > 4 Байт. Как в паскале в тип Integer влезло такое число бит, или же происходит что-то аналогичное Integer Promotion в Си ? Или тип для Integer выделяется больше 4 Байт ?
Первые алгоритмы в целом понятны, вы модифицировали предложенною мной сумму как разность площадей, так действительно лучше.

Сегодня вновь ничего не смогу проверить. Только завтра
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767131
Фотография VSVLAD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вчера решил попробовать решить этого "Вини-пуха" и сделать это наиболее эффективно, и начал с того что самой лучшей попыткой решения является реализация на BASIC (VB6)

IDДатаАвторЯзыкВремяПамятьРазмер104.07.2009 19:35:38Антон ЛунёвBasic0.207218 Кб123
Во-первых, код который просто читает в переменные из файла и записывает решение заняло у меня около ~101 байт (без учетов пробелов, переносов)
Код: vbnet
1.
2.
3.
4.
5.
6.
7.
Sub Main()
    Open "INPUT.TXT" For Input As #1
    Open "OUTPUT.TXT" For Output As #2
        Input #1, m, n, x, y
        Print #2, A;
    Close
End Sub


Остаётся 123 - 101 = 22 байта на формулу (тут циклом боюсь не запишешь) которая даст решение.

Но во-вторых, самое странное, что даже программа которая ничего не делает и не считывает требует около 1,5 Мб памяти, но у решившего получается всего использовано 218 Кб. Я так чую или подвох какой-то (возможно раньше был компилятор у системы), либо фейковый результат...

Может есть какое-то объяснение этому?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767136
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryУ меня такой вопрос. Я дал вам площадку 10^6 на 10^6.
Общая площадь 10^12, это примерно 3.2*12 бит > 4 Байт. Как в паскале в тип Integer влезло такое число бит, или же происходит что-то аналогичное Integer Promotion в Си ? Или тип для Integer выделяется больше 4 Байт ?


Оно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит.

SashaMercuryПервые алгоритмы в целом понятны, вы модифицировали предложенною мной сумму как разность площадей, так действительно лучше.


Последний самый интересный.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767447
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А можно подробнее про операцию "произведения по модулю". Я не понял как вы перемножили большие числа без длинной арифметики и Integer Promotion, в вашем коде я также не заметил специфических операций.

Может быть вы предложите одну формулу для получения нужного результата ?)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767448
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VSVLAD , скорее всего товарищ использовал препроцессорную обработку для сокращения объёма кода
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767483
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryА можно подробнее про операцию "произведения по модулю". Я не понял как вы перемножили большие числа без длинной арифметики и Integer Promotion, в вашем коде я также не заметил специфических операций.


Вот такие объявления
Код: pascal
1.
  тра-та-та: integer;


как раз и являются специфическими операторами. Они определяют сколько бит будет выделено для хранения и работы с переменной, т.е. количество ее возможных значений. Процессору ничего другого не остается, кроме как "крутиться" (здесь это очень точное слово) внутри этого множества значений. Это довольно большая тема, читайте книги или заводите отдельную ветку - поговорим.


SashaMercuryМожет быть вы предложите одну формулу для получения нужного результата ?)


Запросто )
Однако думаю вам это гораздо интереснее будет сделать самостоятельно. В данной задаче это не особенно актуально, но иногда бывает нужно.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767488
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

мне показалось что вы не ответили на мой вопрос



SSУ меня такой вопрос. Я дал вам площадку 10^6 на 10^6.
Общая площадь 10^12, это примерно 3.2*12 бит > 4 Байт. Как в паскале в тип Integer влезло такое число бит, или же происходит что-то аналогичное Integer Promotion в Си ? Или тип для Integer выделяется больше 4 Байт ?

Aleksandr Sharahov,Оно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит.

а в тра-та-та:T
ничего специфического я не вижу ;)

Хотя в коде я не встретил у вас m*n - , потому вполне возможно что переполнения не будет, но тогда почему вы стали говорить про выполнение операций по модулю ?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767489
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если можно получить результат прямой формулой, то это всегда актуально )
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767507
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЕсли можно получить результат прямой формулой, то это всегда актуально )
Гаусс решал задачу о восьми ферзях. Он искал аналитическое решение вида формулы.
И не нашёл. Для шахматных задач (комбинаторный класс задач) иногда и нет
аналитического решения.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38767573
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryа в тра-та-та: ничего специфического я не вижу ;)

А суслик есть, и от него зависит сгенерированный компилятором код.



SashaMercuryХотя в коде я не встретил у вас m*n - , потому вполне возможно что переполнения не будет, но тогда почему вы стали говорить про выполнение операций по модулю ?

Совершенно неважно есть там это умножение или нет. Код, используя целочисленную 32-битную арифметику, каким-то образом считает площадь, превышающую 2^31. Переполнения обязаны быть.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768017
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VSVLAD, а откуда взялась цифра 218 кб? Это что размер исходника? Бинарника? Или выделяемая
память при работе приложения?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768036
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это затрачиваемая программой память, размер кода 123 )

Объясните мне кто-нибудь пожалуйста, каким образом его программа работает с длинной арифметикой, и будет ли она у него на моих примерах ?)

Кстати, Aleksandr Sharahov , зачем вы так усложнили поиск минимального отступа ? Простите, этот код весь ваш, я правильно понимаю ?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768039
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, вы полностью правы в вашем предыдущем рассуждении
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768233
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryAleksandr Sharahov, зачем вы так усложнили поиск минимального отступа?
Специально ничего не усложнял, а проще не сумел )


SashaMercuryПростите, этот код весь ваш, я правильно понимаю ?
Разумеется, весь код, который я здесь привел, написан мной.
В противном случае я сослался бы на автора кода.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768236
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, про Гаусса? Или про прямоугольники?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768582
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По сути, и там и там, но я больше комментировал эту фразу )

mayton Для шахматных задач (комбинаторный класс задач) иногда и нет
аналитического решения.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768583
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov , тогда почему вы мне про переполнение не объясните ?) Раскройте тайну для особо одарённых :D (nolocky, надеюсь вам понятно что это самоирония)

Aleksandr SharahovCellCount1, CellCount2 в вычисляют количество клеток в полных обходах как разность площадей двух прямоугольников M*N и (M-2*LoopCount)*(N-2*LoopCount), а затем делают неполный проход по сторонам внутреннего прямоугольника.

где эта формула в вашем коде ? Я вижу несколько другую
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768618
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Выделил немного времени на изменение предложенного алгоритма.

итак, ваш код.

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
  if LoopCount>0 then Result:=2*(M+N-2*LoopCount)*LoopCount;
  case Direction of
    0: Result:=Result+X-LoopCount;
    1: Result:=Result+Y-3*LoopCount+M-1;
    2: Result:=Result-X-5*LoopCount+2*M+N-1;
    3: Result:=Result-Y-7*LoopCount+2*M+2*N-2;
    end;
  end;



по строчке Result:=2*(M+N-2*LoopCount)*LoopCount пока не буду говорить.
Дальше, мы имеем матрицу со столбцами Result x y LC M N a
Если записать ваш switch одной формулой, мы получим следующее



F(k) числа Фибоначчи 1 1 2 3 ...(нас только первые 4 числа интересуют на самом деле)
[k=4] используется классическая нотация Айверсона (программисты Си знают, а другие могут встретить хорошие разъяснений у Кнута)


В первую очередь мне не нравится тот факт что я использую эту нотацию, так сразу формулу не получил, и сейчас не смогу сидеть и рассуждать, если у вас есть идеи, то пишите. И конечно хочется уйти от F(k)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768620
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SSВ первую очередь мне не нравится тот факт что я использую эту нотацию

Нотация то мне нравится, даже очень :) Мне не нравится, что по факту в программе это ещё один if
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768699
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне не нравится что ты синус используешь для углов кратных четверти.
В этой задаче - он вырожденный и заменяется на более примитивную функцию.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38768756
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryAleksandr Sharahov , тогда почему вы мне про переполнение не объясните ?)
Боюсь, у меня получится хуже, чем пишут в книжках. Возьмите любую хорошую книжку (если не найдете, можно взять почти любую по ассемблеру) и прочитайте про представление чисел в памяти и операции с ними. Сразу все встанет на место.

SashaMercuryAleksandr SharahovCellCount1, CellCount2 в вычисляют количество клеток в полных обходах как разность площадей двух прямоугольников M*N и (M-2*LoopCount)*(N-2*LoopCount), а затем делают неполный проход по сторонам внутреннего прямоугольника.
где эта формула в вашем коде ? Я вижу несколько другую

Попробуйте выполнить вычитание и разложить на множители.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769142
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr SharahovSashaMercuryAleksandr Sharahov , тогда почему вы мне про переполнение не объясните ?)
Боюсь, у меня получится хуже, чем пишут в книжках. Возьмите любую хорошую книжку (если не найдете, можно взять почти любую по ассемблеру) и прочитайте про представление чисел в памяти и операции с ними. Сразу все встанет на место.

SashaMercuryпропущено...

где эта формула в вашем коде ? Я вижу несколько другую

Попробуйте выполнить вычитание и разложить на множители.

1. Не морочьте голову. Ответ на вопрос вы мне так и не дали, на вполне конкретный и обоснованный вопрос. Если я не прав, то пусть меня поправит кто-нибудь другой. Вопрос по переполнению не был раскрыт.

2. Уже давно сделал, и прекрасно вижу различия, только вы говорите одно, в коде пишите совершенно другое. Я вам про это говорю.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769145
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonМне не нравится что ты синус используешь для углов кратных четверти.
В этой задаче - он вырожденный и заменяется на более примитивную функцию.

крайне рад критике, может быть кто-нибудь ещё подскажет альтернативу лучше ?) А также подскажет как уйти от нотации Айверсона и чисел Фибоначчи ?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769152
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SSУже давно сделал, и прекрасно вижу различия, только вы говорите одно, в коде пишите совершенно другое. Я вам про это говорю.

Это к тому, что в коде не видно того что вы отнимаете, и потому не видно алгоритма. Если было бы чётко M*N-() , то ничего бы не спросил
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769153
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymaytonМне не нравится что ты синус используешь для углов кратных четверти.
В этой задаче - он вырожденный и заменяется на более примитивную функцию.

крайне рад критике, может быть кто-нибудь ещё подскажет альтернативу лучше ?) А также подскажет как уйти от нотации Айверсона и чисел Фибоначчи ?
Саш я тоже поднаторел в научных дискурсах и могу кидать софизмы и парадоксы.
Скажи пожалуйста. Это ты у Кнута прочитал про нотацию Айверсона? Ты уверен
что она ДЕЙСТВИТЕЛЬНО необходима для решения задачи Вини-Пуха. Или это
уже новая ветка дискурса с новой задачей?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769288
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нет, про нее я узнал у своего наставника. 8 лет назад. А когда начал изучать Си понял, что вот же она тут :) А у Кнута недавно встретил, он хорошо объясняет. Интернет я не очень люблю, потому не стал рекомендовать гуглить, как это любит Анатолий.

Мне захотелось оптимизировать его код, уйти от ветвлений, потому я предложил такую формулу, но тем не менее в ней ещё есть два ветвления. Разве это не интересно ? Разве задача про ферзей не кажется на первый взгляд такой-же простой как задача про медвежонка ?;)

Меня гонят.. доброго времени суток
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769536
Фотография VSVLAD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

218 кб - выделяемая память приложению. 123 байта - размер исходного кода файла
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769539
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VSVLADmayton,

218 кб - выделяемая память приложению. 123 байта - размер исходного кода файла
Как они меряют? Так точно. Не реально мне интересно.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769631
Фотография VSVLAD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Для меня это останется большой загадкой...
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769827
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, Количество символов (кроме пробелов и переносов строк) и есть размер исходного кода. Вот так меряют. А объём памяти получается исходя из операций аллоцирования(исходя из моих личных наблюдений).




Sharahov, если бы я был неправ, меня бы поправили другие участники. Вы не смогли обосновать свою точку зрения на данную проблему и чётко ответить на поставленный вопрос, и перешли на личные оскорбления. Ваши насмешки мне неинтересны, они только подчёркивают низкие качества вашей личности.



авторОно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит.


Тогда к чему вы приводили мне ответ, если его не было. Я вас спросил, откуда эта цифра (ибо я думал что вы приводите правильный ответ)? Как вообще программа работает ? Вы мне должны были ответить
-эта цифра неправильная, тк переполнение. А не нести ерунду, и устраивать дискут на пустом месте. Всё это время я думал что вы как-то уходите от переполнения и эта цифра, вполне реальная. И я просто не понимал как у вас получается якобы правильный ответ, которого быть не могло. И об этом я вам и талдычил постоянно-"Как ваша функция нашла этот правильный ответ". блаблабла . куча времени потраченного впустую.


И я практически уверен что код не ваш. Вы плаваете в элементарных вопросах.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769858
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Более понятный код:
Код: plaintext
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.
int get_count(int m, int n, int x, int y)
{
	//Distance between point and sides of rectangle {top,right,bottom,left}
	int delta[4] = { y - 1, m - x, n - y, x - 1 }; 
	
	//Find minimum distance
	int k = 0;
	for (int i = 1; i < 4; ++i)
		delta[i]<delta[k] ? k = i: false;
	
	//Characteristics of the inner rectangle
	int n2 = n - 2 * delta[k];
	int m2 = m - 2 * delta[k];
	int sh[4] = { x - delta[k], y - delta[k], m - x - delta[k], n - y - delta[k] };
	//Main 
	int res = m*n-n2*m2;
	switch (k)
	{
	case 0:
		res += sh[0];
		break;
	case 1:
		res += m2 + sh[1] - 1;
		break;
	case 2:
		res += m2 + n2 + sh[2] - 1;
		break;
	case 3:
		res += 2 * m2 + n2 + sh[3] - 2;
		break;
	}
	return res;
}
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769859
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Более понятный код после рефакторинга
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
int get_count2(int m, int n, int x, int y)
{
	//Distance between point and sides of rectangle {top,right,bottom,left}
	int delta[4] = { y - 1, m - x, n - y, x - 1 };

	//Find minimum distance
	int k = 0;
	for (int i = 1; i < 4; ++i)
		delta[i]<delta[k] ? k = i : false;

	//Characteristics of the inner rectangle
	int n2 = n - 2 * delta[k];
	int m2 = m - 2 * delta[k];
	int sh[4] = { x - delta[k], y - delta[k], m - x - delta[k], n - y - delta[k] };
	//Main 
	int t = (k>1);
	int res = m*n - n2*m2 + m2*(k - t) + n2*t + sh[k] - (k - t);
	return res;
}



Единственное что мне тут не нравится, это использование вспомогательной переменной
Код: plaintext
1.
int t = (k>1);
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769921
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я-бы не стал так писать.

Код: plaintext
1.
int t = (k>1);



Лучше-бы так.

Код: plaintext
1.
int t = (k>1)?1:0



или

Код: plaintext
1.
BOOLEAN t = (k>1)?true:false
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769971
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почему так писать не стоит?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769990
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну... в случае если (k>1) дает FALSE - будет (int)0. Для значения true думаю
что возможны варианты ненулевых констант.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769993
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да, вы правы, согласен.
Спасибо :)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769998
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Код: plaintext
1.
BOOLEAN t = (k>1)?true:false


зачем хвост после вопроса? Чем тебе так не нравится:
Код: sql
1.
bool t = (k>1);


в переменную логического типа сохраняем результат логического выражения. Глазами читается нормально.
Если кто-то захочет переменную в арифметический расчет засунуть - это его проблемы.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38769999
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurySharahov, если бы я был неправ, меня бы поправили другие участники. Вы не смогли обосновать свою точку зрения на данную проблему и чётко ответить на поставленный вопрос,

Возможно, другие участники, как, впрочем, и я, не собираются учить Вас программированию за 21 день?

Как-то не хочется всерьез объяснять, что термин "разность" служит для обозначения результата, а сама соответствующая операция называется вычитанием. Устройство ЭВМ, системы счисления, битовые операции и т.п. базовые вещи обязан знать назубок любой начинающий программист. Начните с этого, и, может быть, тогда найдется больше желающих вас поправить.

И еще одно. На форуме вы можете задавать сколько угодно вопросов, но требовать на них ответа вы не можете. Какие задачи мне решать и на какие вопросы мне отвечать, решаете не вы.



SashaMercuryи перешли на личные оскорбления. Ваши насмешки мне неинтересны, они только подчёркивают низкие качества вашей личности.

Где именно вы увидели личные оскорбления в ваш адрес? Ссылку. Вы параноик?



SashaMercuryавторОно и не влезло. Все вычисления выполнены по модулю 2^32. Можно вообще получить отрицательный результат, т.к. старший бит - знаковый. Есть int64, если надо больше бит.

Тогда к чему вы приводили мне ответ, если его не было. Я вас спросил, откуда эта цифра (ибо я думал что вы приводите правильный ответ)? Как вообще программа работает ?
Вы мне должны были ответить-эта цифра неправильная, тк переполнение. А не нести ерунду, и устраивать дискут на пустом месте. Всё это время я думал что вы как-то уходите от переполнения и эта цифра, вполне реальная. И я просто не понимал как у вас получается якобы правильный ответ, которого быть не могло. И об этом я вам и талдычил постоянно-"Как ваша функция нашла этот правильный ответ". блаблабла . куча времени потраченного впустую.


Не совсем так. Даже ребенку очевидно, что ваши исходные данные заставляют программу считать площадь квадрата со стороной 10^5. Правильный ответ, как вам должно быть известно равен 10^10. И само собой разумеется, ни одна программа в мире не сможет поместить его в результат типа integer. Результат вычислений получен в полном соответствии с известным принципом "мякину заложишь - мякину получишь". Правильный ли он? Вы этот вопрос не задавали, и я на него не отвечал. Я отметил лишь, что при вычислениях обязательно было переполнение. Если вы программист, то должны понимать, что в данном случае это означает неверный результат.



SashaMercuryИ я практически уверен что код не ваш. Вы плаваете в элементарных вопросах.

Дайте угадаю. Наверно, он ваш?

Теперь уже похоже на то, что вы успешно окончили курсы "Жизнь за 21 день".
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38770299
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Давайте.... в конструктивное русло. Без личностей.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38770646
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tmayton
Код: plaintext
1.
BOOLEAN t = (k>1)?true:false


зачем хвост после вопроса? Чем тебе так не нравится:
Код: sql
1.
bool t = (k>1);


в переменную логического типа сохраняем результат логического выражения. Глазами читается нормально.
Если кто-то захочет переменную в арифметический расчет засунуть - это его проблемы.
bool не нравится. Нету у нас общего понимания что такое этот бул.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38771066
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr SharahovSashaMercurySharahov, если бы я был неправ, меня бы поправили другие участники. Вы не смогли обосновать свою точку зрения на данную проблему и чётко ответить на поставленный вопрос,

Возможно, другие участники, как, впрочем, и я, не собираются учить Вас программированию за 21 день?



очевидно не собираются.

Aleksandr SharahovКак-то не хочется всерьез объяснять, что термин "разность" служит для обозначения результата, а сама соответствующая операция называется вычитанием. Устройство ЭВМ, системы счисления, битовые операции и т.п. базовые вещи обязан знать назубок любой начинающий программист. Начните с этого, и, может быть, тогда найдется больше желающих вас поправить.

И еще одно. На форуме вы можете задавать сколько угодно вопросов, но требовать на них ответа вы не можете. Какие задачи мне решать и на какие вопросы мне отвечать, решаете не вы.

в этой теме, получалось, что решал я. Правда отвечали вы хреново.


Aleksandr Sharahov
SashaMercuryи перешли на личные оскорбления. Ваши насмешки мне неинтересны, они только подчёркивают низкие качества вашей личности.

Где именно вы увидели личные оскорбления в ваш адрес? Ссылку. Вы параноик?

вы прекрасно понимаете о чём я . ваше сообщение видимо уже удалено.


Aleksandr Sharahov
SashaMercuryпропущено...


Тогда к чему вы приводили мне ответ, если его не было. Я вас спросил, откуда эта цифра (ибо я думал что вы приводите правильный ответ)? Как вообще программа работает ?
Вы мне должны были ответить-эта цифра неправильная, тк переполнение. А не нести ерунду, и устраивать дискут на пустом месте. Всё это время я думал что вы как-то уходите от переполнения и эта цифра, вполне реальная. И я просто не понимал как у вас получается якобы правильный ответ, которого быть не могло. И об этом я вам и талдычил постоянно-"Как ваша функция нашла этот правильный ответ". блаблабла . куча времени потраченного впустую.


Не совсем так. Даже ребенку очевидно, что ваши исходные данные заставляют программу считать площадь квадрата со стороной 10^5. Правильный ответ, как вам должно быть известно равен 10^10. И само собой разумеется, ни одна программа в мире не сможет поместить его в результат типа integer. Результат вычислений получен в полном соответствии с известным принципом "мякину заложишь - мякину получишь". Правильный ли он? Вы этот вопрос не задавали, и я на него не отвечал. Я отметил лишь, что при вычислениях обязательно было переполнение. Если вы программист, то должны понимать, что в данном случае это означает неверный результат.




Когда я давал вам пример, я не подумал что он выйдет за пределы 4Б. Когда прочитал от вас якобы правильный ответ, мне показалось странным, и я решил проверить, корректные ли входные данные я дал.( В целом они были бы корректные, если бы точка находилась ближе к краю, ибо вы не используете M*N в коде.) Оказалось что не корректные. Но ответ вы мне дали ! И я просто пытался узнать откуда он. Вам нужно было написать что он неверный. и всё.
Aleksandr Sharahov
SashaMercuryИ я практически уверен что код не ваш. Вы плаваете в элементарных вопросах.

Дайте угадаю. Наверно, он ваш?

Теперь уже похоже на то, что вы успешно окончили курсы "Жизнь за 21 день".

нет. не мой, но автору спасибо.


PS
Крайне не люблю с кем то ругаться по таким глупым и пустым поводам, вы даже не представляете насколько мне это неприятно. Вы меня не понимаете или я вас не понимаю, в общем-то я сомневаюсь что мы друг другу что-то докажем.(и у меня нет желания). Потому я не буду больше вам отвечать и читать ваши сообщения. Слишком много нехороших настроений. Со своей стороны я себя так не вел по отношению к вам.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38771075
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
С точки зрения логики я написал неверный функции, так будет лучше
Код: plaintext
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.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
int get_count(int m, int n, int x, int y)
{
	//Distance between point and sides of rectangle {top,right,bottom,left}
	int delta[4] = { y - 1, m - x, n - y, x - 1 }; 
	
	//Find minimum distance
	int k = 0;
	for (int i = 1; i < 4; ++i)
		delta[i]<delta[k] ? k = i: false;
	
	//Characteristics of the inner rectangle
	int n2 = n - 2 * delta[k];
	int m2 = m - 2 * delta[k];
	int sh[4] = { x - delta[k], y - delta[k], m - x - delta[k]+1, n - y - delta[k]+1 };
	//Main 
	int res = m*n-n2*m2;
	switch (k)
	{
	case 0:
		res += sh[0];
		break;
	case 1:
		res += m2 + sh[1] - 1;
		break;
	case 2:
		res += m2 + n2 + sh[2] - 2;
		break;
	case 3:
		res += 2 * m2 + n2 + sh[3] - 3;
		break;
	}
	return res;
}

int get_count2(int m, int n, int x, int y)
{
	//Distance between point and sides of rectangle {top,right,bottom,left}
	int delta[4] = { y - 1, m - x, n - y, x - 1 };

	//Find minimum distance
	int k = 0;
	for (int i = 1; i < 4; ++i)
		delta[i]<delta[k] ? k = i : false;

	//Characteristics of the inner rectangle
	int n2 = n - 2 * delta[k];
	int m2 = m - 2 * delta[k];
	int sh[4] = { x - delta[k], y - delta[k], m - x - delta[k]+1, n - y - delta[k]+1 };
	//Main 
	int t = (k>1) ? 1 : 0;
	int res = m*n - n2*m2 + m2*(k - t) + n2*t + sh[k] - k;
	return res;
}



Изменил массив shift
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38771091
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Подумал, что если кто-нибудь не до конца понял алгоритм, лучше добавить рисунок
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38771092
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38771111
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сейчас листки убирал, заметил опечатку у себя. От каждого сдвига на границе внутреннего прямоугольника нужно отнять i, это количество углов внутреннего прямоугольника входящих в этот сдвиг(отнять нужно потому что эта точка дублируется).
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38771294
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[quot SashaMercury]в этой теме, получалось, что решал я. Правда отвечали вы хреново./quot]

У меня совершенно противоположное мнение. Не умеете ни решать, ни вести себя.



SashaMercuryКогда я давал вам пример, я не подумал что он выйдет за пределы 4Б пропущено... Но ответ вы мне дали ! И я просто пытался узнать откуда он. Вам нужно было написать что он неверный. и всё.


Зачем давать тестовый пример, не зная ответа?

Я рассуждал как программист. То что вы дали 2 теста, причем второе значение находится явно вне области допустимых значений параметра меня нисколько не смутило. Вы спросили, что выдает программа в обоих случаях. Я ответил. Какие тут претензии?

Или каждый раз, когда у вас в программе возникает переполнение, вы ищете виновника на стороне?



SashaMercuryнет. не мой, но автору спасибо.

Не стоит благодарности. Код писал больше для себя. Надо же иногда немного расслабиться.



SashaMercuryя не буду больше вам отвечать и читать ваши сообщения.

Правильно, берите только код!
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38772116
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryСейчас листки убирал, заметил опечатку у себя. От каждого сдвига на границе внутреннего прямоугольника нужно отнять i, это количество углов внутреннего прямоугольника входящих в этот сдвиг(отнять нужно потому что эта точка дублируется).
Саш. А как ты себе понимаешь площадь прямоугольника на дискретной поверхности?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38772518
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonSashaMercuryСейчас листки убирал, заметил опечатку у себя. От каждого сдвига на границе внутреннего прямоугольника нужно отнять i, это количество углов внутреннего прямоугольника входящих в этот сдвиг(отнять нужно потому что эта точка дублируется).
Саш. А как ты себе понимаешь площадь прямоугольника на дискретной поверхности?

Как мощность элементов принадлежащих данному прямоугольнику
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38772985
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну... ты ответил умно, но ниочём. Я не то имел в виду.

Представь себе дискретную поверхность пикселов (ячеек, квадратиков e.t.c)
Как ты думаешь, какую площадь должен иметь следующий прямоугольник?

Код: plaintext
1.
Rectangle *rect = new Rectangle(1,1,7,11);



Конструктор задаёт левый верхний и правый нижний угол.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773315
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Можешь нарисовать на клеточной бумаге. Так нагляднее будет.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773323
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В данном прямоугольнике будет 7*11 элементов, потому 77 :)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773326
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Только я исходил из того что это левый нижний и правый верхний.
Рисовать не нужно, я просто только пришёл домой, так бы раньше ответил ))
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773339
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я думаю что его площадь равна 60 квадратикам. Мне так кааатся...
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773355
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если брать за основу точки, то должно быть 77, а если квадратиков, то 60 :) Разве нет ?
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773360
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Точки (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)
7 в одной строке и таких строк 11

А квадратиков будет 6 в строке, 10 строк
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773365
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотя конечно может быть я ошибаюсь, это только мои предположения о том, как можно рассуждать
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773374
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Парадокс заключается в последней фразе
Конструктор задаёт левый верхний и правый нижний угол.
Это вопрос договорённостей. Как мы договоримся задавать ректенжл - так и будет.
Будем ли мы привязывать. Это как договорённости о право-сторонней (правило буравчика)
или лево-сторонней системе координат (x,y,z) в 3-d графике.

Это как наша договорённость о том как считать subsring(begin, end).

Вот мне моё техническое чутьё подсказывает что over 50% графических библиотек
2D графики используют мой вариант толкования прямоугольника.

Код: java
1.
new Rectanle(x1,y1,x2,y2);



Здесь прямоугольник включает в себя x1,y1 но не включает точку x2,y2.
Она лежит ВНЕ прямоугольника в том силе и правый и нижний отрезок
прямоугольника.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773389
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это может показаться странным но если мы переходим к непрерывности
на плоскости (координаты - дробные) то всё становиться на смои места.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773411
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это интересно. Хотя некоторые моменты мне не до конца понятны, но скорее это связано с тем что уже слишком поздно. Спасибо, я обязательно учту всё это :)
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773427
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати в задаче о блуждающем Винни-пухе можно использовать подсчёт отрезков
как прямоугольников с единичным измерением или делать вычитание площадей
если это оптимизирует задачу по скорости и не противоречит смыслу.

Мне кажется что на восточном направлении обхода сада ВинниПух
может учитывать площадь по более простой формуле.
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773485
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Буду рад любым предложениям по оптимизации )

У меня в голове крутится другой метод, хочу привести его путь к уравнению архимедовой спирали, и вычислять длину её дуги. Общая идея мне понятна, а возможно ли это сделать и как, пока не решил. Думаю что так решить можно.

Меня гонят. Доброго времени суток C:
...
Рейтинг: 0 / 0
Обход прямоугольника по спирали. Поиск более подходящего алгоритма
    #38773507
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Там с длиной дуги не очень красиво получается. Особенно с учотом того
что у нас не квадрат а прямоугольник. Ломается монотонность числового ряда.

Хотя... попробуй.
...
Рейтинг: 0 / 0
88 сообщений из 88, показаны все 4 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Обход прямоугольника по спирали. Поиск более подходящего алгоритма
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]