Форум PHP программистов > Как найти стороны прямоугольника

[ Поиск ] - [ Пользователи ] - [ Календарь ]

Полная Версия: Как найти стороны прямоугольника

kaww

4.11.2016 - 20:25

Такая задача. Нужно сгенерировать поле, состоящее из известного количества секций (как таблица), максимально близкое к квадрату.
Например:
1. Секций - 20, тогда поле будет 5х4
2. Секций - 100, поле - 10х10
3. Секций - 17, поле - 17х1

Очевидным кажется вариант - это разложить число на множители и выбрать нужные. Но что-то мне подсказывает, что есть вариант оптимальнее?

AllesKlar

4.11.2016 - 20:41

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

Секций 50
наибольший квадрат: 7^2 = 49
Первая сторона = 7
Вторая сторона: 50 - 49 = 1
1 / 9 = 0 (рядов еще) но осталось 1 секция, значит берем следующий возможный квадрат

6^2 = 36
Первая сторона = 6
Вторая сторона: 50 - 36 = 14
14 / 6 = 2 (ряда еще) но осталось 2 секции, значит берем следующий возможный квадрат

5^2 = 25
Первая сторона = 5
Вторая сторона: 50 - 25 = 25
25 / 5 = 5 (рядов еще)
Прямоугольник: квадрат 5х5 + 5 рядов сверху = 5х10

_____________
[продано копирайтерам]

Valick

4.11.2016 - 20:50

kaww, квадрат - это равнозначные стороны, количество секций - это делимое, следовательно ищем минимальное расхождение делителя и частного.
100 делим в цикле начиная с 2, и сравниваем затем сохраняем число 50-2 = 48
то что не делиться без остатка пропускаем, как только получаем 0 (10-10) значит нашли золотую середину (то бишь квадрат), если получили отрицательный ответ, то берём предыдущий результат.

_____________
Стимулятор ~yoomoney - 41001303250491

kaww

4.11.2016 - 21:02

AllesKlar, выглядит хорошо, спасибо. Пока не попадется простое число:
1. сторона - 4
2. 17 - 16 = 1
3. 1 / 4 = 0 (1)
4. сторона - 3
5. 17 - 9 = 8
6. 8 / 3 = 2 (2)
.....
n. сторона - 1
n+1. 17 / 1 = 17
n+2. 17 - 17 = 0
Хотя, все так же круто )
З.Ы. для 50 наибольший квадрат - это 7^2=49).

Valick

4.11.2016 - 21:04

Цитата (kaww @ 4.11.2016 - 20:02)

для 50 наибольший квадрат - это 7^2=49

но остаётся одна секция, следовательно этот вариант не вариант

_____________
Стимулятор ~yoomoney - 41001303250491

Ron

4.11.2016 - 21:04

А вот так?


$a = 18;

$fillRectangleSide = ceil(sqrt($a));
$firstSide = 1;

for ($i = $fillRectangleSide; $i > 0; $i--) {
    if ($a % $i == 0) {
        $firstSide = $i;
        break;
    }
}

$secondSide = $a/$firstSide;

echo "$firstSide x $secondSide";

kaww

4.11.2016 - 21:11

Цитата (Valick @ 5.11.2016 - 00:04)

но остаётся одна секция, следовательно этот вариант не вариант

Конечно, это означает лишь то, что расчет начинается не с 36 а с 49 в алгоритме AllesKlar

Valick

4.11.2016 - 21:14

kaww, на самом деле Ron всё "испортил", я хотел что бы у тебя родился его вариант в процессе оптимизации моего варианта))

_____________
Стимулятор ~yoomoney - 41001303250491

Ron

4.11.2016 - 21:37

Цитата (Valick @ 4.11.2016 - 21:14)

kaww, на самом деле Ron всё "испортил"

Да? Ну ладно. =) Глянул мельком, вроде не было такого решения. Не вчитывался, интересно было самому решить.

Какая-то лютая задачка для 5-го класса! А если секций 24571 как это посчитать школьнику без калькулятора, что называется, "на руках"? Не представляю.

kaww

4.11.2016 - 21:51

Цитата (Valick @ 5.11.2016 - 00:14)

Ron всё "испортил"

спасибо ему за это ). Даже как-то неловко, что не пришел сам к такому решению (хотя, особо и не ходил никуда ;) ) . Зато сделал тест всех предложенных вариантов:

test


$v = 3571;

$start = microtime(true);
for($i=0;$i<10000;++$i) {
	$h = (int)sqrt($v);
	while($h > 1) {
		$d = $v - $h*$h;
		if (!$d) {
			break;
		}
		if (!($d%$h)) {
			$h += $d/$h;
			break;
		}
		--$h;
	}
	// var_dump($v / $h, $h);
}

echo 'AllesKlar: ', (microtime(true) - $start), PHP_EOL;

$start = microtime(true);
for($i=0;$i<10000;++$i) {
	$w = 2;
	$_w = 1;
	while($w < $v) {
		if (!($v%$w)) {
			if (0 === ($_t = (int)($v/$w) - $w)) {
				break;
			}
			if ($_t < 0) {
				$w = $_w;
				break;
			}
			$_w = $w;
		}
		++$w;
	}
	// var_dump($w, $v / $w);
}
echo 'Valick: ', (microtime(true) - $start), PHP_EOL;


$a = $v;
$start = microtime(true);
for($i=0;$i<10000;++$i) {
	$fillRectangleSide = ceil(sqrt($a));
	$firstSide = 1;

	for ($ii = $fillRectangleSide; $ii > 0; $ii--) {
	    if ($a % $ii == 0) {
	        $firstSide = $ii;
	        break;
	    }
	}

	$secondSide = $a/$firstSide;
	// var_dump($firstSide, $secondSide);
}
echo 'Ron: ', (microtime(true) - $start), PHP_EOL;

Который дал следующие результаты:
AllesKlar: 0.56197690963745
Valick: 15.700574159622
Ron: 0.3719470500946

Быстрый ответ:

Здесь расположена полная версия этой страницы.