Fonction binaire récursive à décimale sans pow() ou boucles

Je fais un cours C. Je dois faire un binaire XOR récursif mais j'ai quelques limitations. Je ne peux pas utiliser de fonctions loop ou math.h, et je ne peux pas non plus appeler une autre fonction de la fonction XOR.Fonction binaire récursive à décimale sans pow() ou boucles

C'est le prototype de la fonction:

int binaryXor(int firstnumber[], int secondnumber[], int length);

où firstNumber et secondNumber sont des tableaux avec la même longueur de 1 et de 0 et de longueur est leur longueur.

La fonction doit renvoyer la valeur décimale du XOR de ces deux tableaux. Faire le XOR est assez simple, mais comment puis-je le convertir en décimal avec toutes les limitations?

Source

2009-11-30 Ariel

Cette fonction ne renvoie pas une « valeur décimale » de quoi que ce soit, il retourne un entier. –

Logiquement est-il possible de traiter chaque élément d'un tableau sans que le processus soit une boucle? –

Dans le contexte d'une affectation de cours, je suis presque certain que si l'on vous dit d'écrire une "fonction récursive" et que vous "ne pouvez pas utiliser de boucles", il s'ensuit qu'un appel récursif n'est pas une boucle. Vous pouvez ou ne pouvez pas être d'accord avec cette définition de boucle, mais je suis assez sûr qu'ici, cela signifie n'importe quelle construction de boucle procédurale. –

Il s'agit d'une question récursive standard. L'astuce consiste à réaliser que la valeur entière d'une chaîne de 1 et 0 suivi de 1 ou 0, est 2 * la valeur entière de la chaîne plus la valeur du chiffre.

Vous voulez faire quelque chose comme

if(length <= 0) return 0; 

return 2 * binaryXOR(firstnumber, secondnumber, length - 1) + (firstnumber[length - 1]^secondnumber[length - 1]);

Source

2009-11-30 18:08:26 UncleO

Quelle est la préséance relative de '+' et '^'? Alors pourquoi votre expression donne-t-elle la mauvaise réponse? Utilisez des parenthèses (parenthèses) lorsque vous mélangez des opérations arithmétiques et binaires! –

Merci Jonathan. D'habitude, je ne teste pas ces réponses aux devoirs. Le PO peut apprendre quelque chose de mes erreurs! – UncleO

Merci beaucoup, votre aide m'a beaucoup aidé. – Ariel

Un appel de fonction récursif peut être utilisé à la place d'une boucle.

Source

2009-11-30 18:02:39

True - Je déteste ces sortes de problèmes. Qui utiliserait la récursion pour parcourir un tableau? –

En C, personne. Dans les langues fonctionnelles, tout le monde. Donc sans doute oui, l'école devrait enseigner la récurrence soit avec un langage fonctionnel ou un exemple plus naturel. Mais une récursion qui n'est pas trivialement réductible à une boucle n'est pas récursive en queue, et les problèmes qui ne peuvent pas être récursifs en queue peuvent être un peu au-delà du niveau du cours au début où la récursivité est introduite.Au moins, je suppose que c'est la réflexion qui mène à ces missions «faites quelque chose que vous ne feriez jamais vraiment, juste pour illustrer un point». –

Pour écrire une fonction récursive, sans boucles, vous devez répondre à la question suivante: « Comment puis-je exprimer la réponse à mon problème en termes d'un plus petit problème »

Dans ce cas, le problème est que vous avez length chiffres à regarder, mais vous n'êtes pas autorisé à boucler. Alors, comment exprimez-vous un xor de taille length en termes de plus petit xor, avec une certaine quantité de travail qui ne nécessite pas de boucle? [Edit: accrochez-vous, il suffit de regarder à nouveau votre question, et vous dites que vous avez déjà trié xor, donc je suppose que vous avez déjà fait cela. Dans ce cas, mon commentaire ci-dessus est la seule chose que vous devez savoir: vous avez terminé. Un int en C n'est pas une valeur décimale, c'est juste une valeur. Vous n'avez pas besoin de convertir quelque chose en décimal pour le stocker ou le renvoyer dans un int.

Si cela vous intéresse cependant, je peux poster un code qui convertit un entier en une valeur décimale en utilisant une fonction récursive. Un moyen simple est de calculer le nombre de chiffres requis, en comparant avec des puissances de plus en plus grandes de 10, puis de reculer les chiffres en commençant par la fin.]

Source

2009-11-30 18:03:23

Fonction binaire récursive à décimale sans pow() ou boucles

Répondre

Questions connexes