Maison > développement back-end > tutoriel php > Trouver la somme des plus grands diviseurs impairs en utilisant PHP

Trouver la somme des plus grands diviseurs impairs en utilisant PHP

青灯夜游
Libérer: 2023-04-08 14:10:01
avant
2994 Les gens l'ont consulté

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.

Trouver la somme des plus grands diviseurs impairs en utilisant PHP

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);
Copier après la connexion

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

Trouver la somme des plus grands diviseurs impairs en utilisant PHP

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!

Étiquettes associées:
php
source:csdn.net
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal