Trouver la somme des plus grands diviseurs impairs en utilisant PHP

Cet article explique comment trouver la somme des plus grands diviseurs impairs en utilisant PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il sera utile à tout le monde.

Xiao Yi est un passionné de théorie des nombres et s'intéresse beaucoup aux diviseurs impairs d'un nombre. Un jour, Xiaoyi a rencontré un tel problème : définissez la fonction f(x) comme le plus grand diviseur impair de x, et x est un entier positif. Par exemple : f(44) = 11.

Maintenant étant donné un N, nous devons trouver f(1) + f(2) + f(3)…….f(N)

Par exemple : N = 7

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

Xiao Yi a rencontré des difficultés pour calculer ce problème et a besoin de vous pour concevoir un algorithme pour l'aider.

<?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);

Commencez avec la pensée conventionnelle, qui a été déboguée, expire toujours si vous la remplacez par la méthode 2, elle expire toujours.

Changez votre façon de penser. .

Dans le processus de recherche de somme(i), si i est un nombre impair, vous pouvez le trouver directement, qui est i lui-même, c'est-à-dire f(i) = i.

Le problème est de trouver la somme de tous les f(i), i est un nombre pair.

Parce que c'est le plus grand diviseur impair, donc f(2k) = f(k), donc f(2) + f(4) + … + f(2k) = f(1) + f( 2 ) + … + f(k);

Par conséquent, il n'est pas facile de penser à la formule générale

en utilisant l'induction mathématique. . . Une telle question BT. .

Cet article est reproduit à partir de : https://blog.csdn.net/qq_28602957/article/details/77914402

Apprentissage recommandé : Tutoriel vidéo PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!