Мне нужно получить два фактора (x, y) заданного числа (n), такие, что:
Примеры:
Любой язык будет делать, но предпочтительно php.
РЕДАКТИРОВАТЬ – ПОДТВЕРЖДЕНИЕ
Я хочу создать прямоугольник, x единиц шириной * y единиц, таких, что его площадь как можно ближе к n. x и y должны быть целыми числами. Если n – простое число, то коэффициенты n – 1 допустимы.
Ваши спецификации были недостаточно точными. Вы заявили, что вам нужны факторы, но в вашем тестовом примере 4 не является фактором 17
Следующий псевдокод работает с приоритетом того, что один фактор является точным
for i in range(ceiling(sqrt(n)), 1){ if ( n modulo i ) == 0 { x = i y = round(n/i) } } Там, где простая инструкция sqrt будет работать для обеспечения максимально возможного числа чисел, но не гарантирует, что они являются факторами.
x = y = round( sqrt(n) )
Вам нужно решить, насколько важны ваши три правила.
Возможность 1: если х * у, будучи как можно ближе к n, истинно, тогда n = 17 => 1,17, а не 4,4. В этом случае вы хотите факторизацию, и есть много способов сделать это, но такой код прост:
for(i = floor(sqrt(n)) .. 1) { if n % i ==0 { x = i; y = n/x; break; } }
Возможность 2: если быть ближе друг к другу, более важно, вы ожидаете, что n = 18 => 4,4, а не 3,6, и этот код будет работать. Это, однако, не является фактором.
x=floor(sqrt(n)) y=floor(n/x)
Проблема, как написано, неразрешима без четкой спецификации.
EDIT ————
Теперь спецификация была отредактирована, теперь она определена, но вам нужно сделать «Возможность 1», посмотреть, является ли результат простым (1 является одним из значений), а затем, если повторение делает возможность 2. Однако я сомневаюсь, что это то, что какой бы учитель не писал это как домашнее задание.
$num = ...; // some number if (is_prime($num)) // implement the is_prime() function yourself --$num; // Subtract to get an even number, which is not a prime $candidates = array(); // Numbers that may fit. $top_search = $num / 2; // Limits the useless search for candidates for($i=1; $i < $top_search; ++$i) { if ($num % $i == 0) $candidates[$i] = $num / $i; } // Now, check the array in the middle
Идея от меня (более псевдо-php)
$root = sqrt($inputNumber); $x = floor($root); $y = floor($root); if(($root - $x) > 0.5) $y++;
У меня были бы все факторы, записанные в массив, используя следующий код.
#Application lists all factors/divisors for a number. targetNumber=input('What number do you want the factors for?\n> ') factors=[] for i in range(1,targetNumber): if targetNumber%i==0: factors.append(i) elif targetNumber/i==1: factors.append(targetNumber) break print factors
Затем я перебираю массив, чтобы проверить, какие из них действительно могут быть использованы. Подробнее об этом алгоритме см. http://pyfon.blogspot.com.au/2012/09/list-factors-of-number-in-python.html.
Вот функция PHP, которая определяет приоритеты двух «факторов», близких друг к другу, с точными факторами:
function weird_factors($ori) { $sq = intval(sqrt($ori)); $start = $sq - 10; $end = $sq + 10; $n = 0; for ($s = $start; $s <= $end; $s++) { for ($t = $start; $t <= $end; $t++) { $st = $s * $t; if ($st <= $ori and $st > $n) { $n = $st; $ns = $s; $nt = $t; } } } return array($ns, $nt); }
Напишите программу, чтобы найти коэффициент любого числа
<?php if(isset($_POST['sub'])) { $j=0; $factor=array(); $num=$_POST['nm1']; for($i=1;$i<=$num;$i++) { if($num%$i==0) { $j++; $factor[$j]=$i; } } } ?> <table> <form name="frm" method="post" action=""> <tr> <td>Number:</td> <td><input type="text" name="nm1" /></td> </tr> <tr><td></td><td><input type="submit" name="sub" /></td> <td><center><span> <?php if(isset($_POST['sub'])) { echo "Factors are :";for($i=1;$i<=count($factor);$i++) { echo $factor[$i].","; } } ?> </span></center></td></tr> </form> </table>