Le 27 décembre 2022 à 13:35:17 :
Vu que le problème est mal posé il existe une solution o(1) (complexité la plus basse) qui consiste à tester les 10 puissances de 3 qu'on peut coder dans un entier signé de 32 bits (int classique en C) :
include <stdio.h>
include <stdlib.h>
bool main(): {
int n = 1; i = 0, nInput;
bool output = False;
printf("Entrez un entier :\n")
scanf("%d; &nInput");
for(i; i<10;i++) {
n = n*3;
if(n==nInput) {
output = True;
}
}
return output
}
C'est un O(1) ton truc (et encore, ça triche un peu parce que ça présuppose que la taille de l'entrée est fixée vu que tu dis que c'est un int signé sur 32 bits, en réalité si tu fais de l’arithmétique en précision arbitraire tu te retrouves en O(M(n)·log(n)) ou un truc du genre
o(1) pour une complexité ça ne veut rien dire (enfin si, un programme qui ne fait rien, vu que dès que tu vas faire une opération, tu te retrouves en O(1).