ホームページ > バックエンド開発 > PHPチュートリアル > PHP を使用して最大の奇数の合計を求める

PHP を使用して最大の奇数の合計を求める

青灯夜游
リリース: 2023-04-08 14:10:01
転載
2993 人が閲覧しました

この記事では、PHP を使用して最大の奇数の約数の合計を求める方法を紹介します。一定の参考値があるので、困っている友達が参考になれば幸いです。

PHP を使用して最大の奇数の合計を求める

Xiao Yi は数論の愛好家で、数の奇数の約数に非常に興味があります。ある日、Xiaoyi は次のような問題に遭遇しました。関数 f(x) を x の最大の奇数約数として定義し、x は正の整数です。例: f(44) = 11.

N が与えられた場合、f(1) f(2) f(3)…….f(N)

を見つける必要があります。例: N = 7

f(1) f(2) f(3) f(4) f(5) f(6) f(7) = 1 1 3 1 5 3 7 = 21

Xiaoyi はこの問題の計算で困難に直面したため、彼を助けるアルゴリズムを設計する必要があります。

<?php
$num = trim(fgets(STDIN));

function jNum($num){
        $m = $num/2;
        $res = 1;
        if($num&0x1 == 1){//如果他本身就是个奇数,那么他的最大奇约数就是他本身
                $res = $num;
                goto HELL;
        }
        for($i = 1; $i<=$m; $i=$i+2){//如果不是,那么就从1开始一直往上除,每次+2(奇数)
                if($num%$i==0){
                        $res = $i;
                }
        }
        HELL:
        return $res;
}

function jNum2($num)
{
        $res = 0;

        for($i=1;$i<=$num;$i++){
                if(($i&0x1) == 1){//如果他本身就是个奇数,那么他的最大奇约数就是他本身
                        $res+=$i;
                }else{
                        $n = $i;
                        while(true){//优化,从最大的数开始往下除
                                $n = $n>>1;
                                if(($n&0x1) == 1){
                                        $res+=$n;
                                        break;
                                }
                        }
                }
        }

        HELL:
        return $res;
}

function jNum3($num){//公式法
        if($num == 1){
                return 1;
        }
        if(($num&0x1) == 0){
                return jNum3($num>>1)+$num*$num/4;
        }else{
                return jNum3($num-1)+$num;
        }

}
//$sum = 0;
//for($i = 1; $i<=$num; $i++){
//      $sum+=jNum($i);
//}
//echo $sum;

//echo jNum2($num);

echo jNum3($num);
ログイン後にコピー

従来の考え方から始めます。デバッグ済みの方法 1 は常にタイムアウトします。方法 2 に変更しても、やはりタイムアウトします。本質的な違いはありません。

考え方を変えてください。 。

sum(i) を求める過程で、i が奇数の場合は、i そのもの、つまり f(i) = i を直接求めることができます。

問題は、すべての f(i) の合計を見つけることです。i は偶数です。

これは最大の奇数であるため、 f(2k) = f(k) したがって、 f(2) f(4) … f(2k) = f(1) f(2) … f ( k);

したがって、数学的帰納法で得られる一般式を考えることは容易ではありません。 。 。 BTのような質問です。 。

PHP を使用して最大の奇数の合計を求めるこの記事は次から転載されています: https://blog.csdn.net/qq_28602957/article/details/77914402

推奨される学習:
PHP ビデオ チュートリアル

以上がPHP を使用して最大の奇数の合計を求めるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル:
php
ソース:csdn.net
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート