En parcourant les protocoles d’interview pour la position du développeur, j’ai découvert le problème suivant: «Offrir un code qui imprimerait des nombres dans l’ordre décroissant de n à 0, sans utiliser d’opérateurs de comparaison (cachés ou explicites) (la mise en œuvre de la fonction d’impression ne compte pas)». Malgré le fait que cette tâche n'avait rien à voir avec moi, cela m'a occupé et j'ai décidé de réfléchir à des moyens de la résoudre (bien que je ne sache toujours pas qui et quand résoudre quelle tâche aurait besoin de cette méthode d'optimisation de code).
La première chose qui m'est venue à l'esprit était d'essayer d'utiliser des modèles. Comme ça
template<int n> void print() { printf("%d\n", n); print<n - 1>(); } template<> void print<0>() { printf("0\n"); } int main(int argc, char* argv[]) { print<N>(); return 0; }
Le problème est que la programmation est une discipline d'ingénierie, pas une discipline occulte, et si "quelque chose" doit se produire dans le système, alors "il" doit être décrit et des ressources doivent être allouées pour cela, et dans ce cas, puisque le développement de modèles a lieu au stade de la compilation, il y a des restrictions sur l'imbrication de telles constructions (et c'est bon et correct, et Dieu merci, c'est le cas), et le compilateur a très justement émis "erreur fatale C1202: contexte récursif de dépendance de type ou de fonction trop complexe" avec une taille N plus grande 2000.
La prochaine chose qui m'est venue à l'esprit était d'utiliser la méthode classique avec des pointeurs vers des fonctions.
typedef void(*PrintFunc)(int); void printZero(int); void printNumber(int n); PrintFunc g_functors[] = {printZero, printNumber}; void printZero(int) { printf("0\n"); } void printNumber(int n) { printf("%d\n", n--); g_functors[!!n](n); } int main(int argc, char* argv[]) { printNumber(N); return 0; }
Mais même alors, les restrictions imposées par la loi de la nature se sont fait sentir, et comme l'imbrication des appels de fonction est limitée par la taille de la pile, un "débordement de pile" légitime a été obtenu avec une valeur de N> 4630.
À cet endroit, la déception et la colère m'ont complètement envahi et j'ai réalisé que pour une solution complète à ce problème, vous ne devez éviter rien, y compris les trucs les plus sales. Le problème est que pour certaines valeurs de N, nous devons transférer le contrôle aux sections nécessaires du code. Et ce n'est pas un problème lorsque nous avons des déclarations conditionnelles à notre disposition, mais quand elles ne sont pas là, nous devons recourir à la sorcellerie. Dans les temps anciens, cela pouvait être résolu en utilisant la méthode goto, mais depuis lors, les chasseurs de sorcières et autres combattants de dragons ont sévèrement limité sa fonctionnalité (et c'est aussi bon et juste) et nous aimerions écrire quelque chose comme ça
g_functors[0] = [](int){print("0\n"); goto end; } g_functors[1] = [](int n){print("%d\n", n); goto begin; } begin: g_functors[!!n](n--); end:
mais nous ne pouvons pas.
Par conséquent, bien qu'il m'ait été interdit de m'engager dans la magie noire, dans ce cas j'ai décidé de faire une exception en ajoutant un peu de magie à l'exemple précédent.
void printZero(int); void printNumber(int n); PrintFunc g_functors[] = {printZero, printNumber}; void printZero(int) { printf("0\n"); throw 0; } void printNumber(int n) { printf("%d\n", n); } int main(int argc, char* argv[]) { int n = N; try{ begin: g_functors[!!n](n--); goto begin; } catch (...){} return 0; }
Et cela a complètement résolu le problème (pour tout N).
PS: je serai heureux d'entendre parler d'autres méthodes pour résoudre ce problème