Path: ...!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!.POSTED!not-for-mail From: Olivier Miakinen Newsgroups: fr.sci.maths Subject: =?UTF-8?Q?[Ma_r=c3=a9ponse]_Re:_Probl=c3=a8me_de_l'arr=c3=aat?= Date: Fri, 30 Sep 2022 22:48:46 +0200 Organization: There's no cabale Lines: 60 Message-ID: References: <63367bdd$0$25804$426a74cc@news.free.fr> NNTP-Posting-Host: 220.12.205.77.rev.sfr.net Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 8bit X-Trace: cabale.usenet-fr.net 1664570926 10943 77.205.12.220 (30 Sep 2022 20:48:46 GMT) X-Complaints-To: abuse@usenet-fr.net NNTP-Posting-Date: Fri, 30 Sep 2022 20:48:46 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.4 In-Reply-To: Bytes: 3211 Le 30/09/2022 12:53, j'écrivais : >> >> def f(m, n): >> while n: >> m, n = m ^ n, (m & n) << 1 >> return m > > [...] > > Lorsque l'un des nombres est négatif, il arrive que l'algorithme ne > s'arrête jamais. Par exemple lorsque m vaut -1 et que n vaut n'importe > quel nombre strictement positif. > > Ma question est alors de déterminer pour quelles valeurs de m et n > le programme s'arrête et pour quelles valeurs il ne s'arrête jamais. > > Question subsidiaire : lorsque le programme s'arrête, combien de > tours de boucle a-t-il réalisés ? Voici ma réponse à cette question, sur un exemple. Voyons par exemple f(-123350, 19676). En binaire, les nombres -123350 et 19676 s'écrivent respectivement de la façon suivante, où les « ... » du début indiquent que les 1 ou les 0 sont à imaginer comme s'étendant jusqu'à l'infini vers la gauche : ...11100001111000101010 ...00000100110011011100 Mettons une barre de séparation à droite de chaque colonne de chiffres égaux (soit deux 0 l'un au dessus de l'autre, soit deux 1 l'un au dessus de l'autre) : ...1110|0|00|11|1|10|00101|010| ...0000|0|10|01|1|00|11011|100| Ne retenons que les blocs se terminant par une colonne de deux 1 : |11|1| |00101| |01|1| |11011| On a ici un bloc de longueur 2, un bloc de longueur 1 et un bloc de longueur 5. Ma proposition est que le nombre de tours de boucle sera toujours exactement égal à un de plus que la plus grande longueur de bloc retenu. Dans cet exemple, ce sera donc 5 + 1 = 6 tours de boucle. Plus généralement : - Si n = 0, on fera 0 tour de boucle. - Sinon, si on ne retient aucun bloc, on fera 1 tour de boucle. - Sinon, soit l_max la longueur du plus grand bloc retenu, on fera (l_max + 1) tours de boucle. Notons qu'il peut y avoir plusieurs blocs de longueur l_max, ça ne changera rien au résultat. Cas particulier, si l'un des nombres (mettons m) est négatif, et que l'autre (donc n) est positif et supérieur ou égal à -m, alors le bloc le plus à gauche est de longueur infinie. Dans ce cas, et dans ce cas seulement, le programme boucle indéfiniment. -- Olivier Miakinen