팩토리얼을 이용한...
아래의 문제의 답을 도출하는 과정을 프로그래밍 언어로 구현하시오.(php, javascript... 뭐든 좋습니다)
5! 이란 5 * 4 * 3* 2 *1 를 의미합니다. 따라서 5! =120 이 됩니다.
! 은 "팩토리얼" 이라고 읽습니다.
145 라는 수에 대해, 그 각자리 숫자를 분해하여 !(팩토리얼) 을 붙이고 그 결과를 더해보면..
즉 수식으로 표현해보면
1! + 4! + 5! = 1 + 24 + 120 = 145 가 되어. 분해하기 전 원래 숫자가 나옵니다
문제) 145와 같이 각 자리 숫자를 분해하여 !(팩토리얼) 을 붙이고 그 결과를 모두 더했을 때 원래의 수와 똑같이 나오는 모든 수를 구하시오.
|
댓글을 작성하시려면 로그인이 필요합니다.
댓글 3개
set_time_limit(0);
//ini_set('memory_limit','1G');
header('Content-Type: text/html; charset=utf-8');
function microtime_float() {
list($usec, $sec) = explode(" ", microtime());
return (((float)substr((string)$usec, 0, 4) + (float)$sec)) * 1000;
}
function get_excute_time($msg, $start_time){
$end_time = microtime_float();
$time = ($end_time - $start_time) / 1000;
echo "$msg : $time seconds" . PHP_EOL ;
}
$start_time = microtime_float();
//0부터 9까지의 각 펙토리얼의 값을 저장해 놓는다. 재사용
$facts = Array(0 => 1, 1 => 1);//0!은 1이다.
for ($i = 2; $i < 10; $i++) {
$facts[$i] = $facts[$i - 1] * $i;
}
print_r($facts);
//1자리 부터 10 자리 까지의 각 펙토리얼의 값의 합중 최대값만 저장해놓는다. 범위를 알기 위해서
//9, 99, 999 ..... 9999999999
$maxs = Array(1 => $facts[9]);
for ($i = 2; $i <= 10; $i++) {
$maxs[$i] = $maxs[$i - 1] + $facts[9];
}
print_r($maxs);
//각자리수의 최대값을 초과한 숫자는 의미가 없다.
$find = Array();
$i = 0;
while(1){
$j = (string)$i;
$j_length = strlen($j);
if ($i > $maxs[$j_length])
break;
$sum = 0;
for ($k = 0; $k < $j_length; $k++){
$sum += $facts[$j[$k]];
}
if ($i == $sum)
$find[] = $i;
$i++;
}
print_r($find);
get_excute_time("진행 시간", $start_time);
?>
(
[0] => 1
[1] => 2
[2] => 145
[3] => 40585
)
진행 시간 : 2.52 seconds
좋은 답변 감사합니다~