0
votes

Comment trouver le nombre manquant sans utiliser de tableaux?

Je dois trouver un nombre manquant dans une séquence de nombres. L'entrée se compose d'un entier positif n, compris entre 0 et 35 000, et de n nombres uniques de plage [0..n]. (Cette plage contient donc n + 1 nombres).

J'ai déjà essayé certaines choses avec sum = {n * (n + 1)} / 2 puis misNum = sum-SumOfNum ; , mais je n'ai pas trouvé de moyen de faire fonctionner cela.

J'ai écrit du code, mais pas avec les exemples que j'ai mentionnés précédemment. Évidemment, ce code n'est pas complet, mais je ne sais pas comment le rendre complet.

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *v[])  {
    int length;
    int num; 

    scanf("%d", &length);
    /*scanf(???)*/

    int goal=length;
    int i;

    for(i=0; i!=length; i++){
        goal=goal+i-num[i];
    };
   return goal;
}

L'entrée et le résultat devraient être:

Entrée: 2 "enter" 0 2. Sortie: 1

Entrée: 3 "enter" 0 3 1. Sortie: 2

c arrays numbers sequence

2 commentaires

Devez-vous vérifier que la séquence de nombres correspond à l'attente, c'est-à-dire que les nombres sont dans la bonne plage, que leur décompte est correct et que vous n'avez pas de nombres en double? (Le dernier peut être impossible sans utiliser un tableau.)

Mais le doublon possible est pour C # et non C.

3 Réponses :

3
votes

La somme de tous les nombres de 0 à n est

n (a1 + an) / 2 = (dans votre cas a1 = 0 et an = n + 1) n * (n + 1) / 2

donc le nombre manquant est n * (n + 1) / 2 - (somme des nombres d'entrée après la longueur)

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* v[]) {
    int length;
    int i = 0;
    int sum = 0;

    scanf_s("%d", &length);

    // calculate arithmetic series sum
    auto series_sum = ((length + 1) * (length)) / 2;

    while (i < length)
    {
        int next;
        scanf_s("%d", &next);

        sum += next;
        ++i;
    }

    printf("missing num is %d ", series_sum - sum);
}

0 commentaires

1
votes

Vous avez n nombre d'entiers à analyser. Utilisez l'équation mathématique pour calculer la somme du premier < code> n + 1 nombres naturels . Ensuite, exécutez une boucle pendant n fois, puis exécutez une boucle pour ajouter tous les n nombres scannés. Puis soustrayez cette somme avec la somme de n + 1 nombre naturel. Le résultat sera le nombre manquant.

0 commentaires

0
votes

Le calcul à partir de la question est également correct et peut fonctionner avec quelques modifications.

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *v[])  {
    int length;
    int num; 

    // printf("enter maximum number: ");
    scanf("%d", &length);

    int goal=length;
    int i;

    for(i=0; i!=length; i++){
        // printf("number[%d]: ", i);
        if(scanf("%d", &num) != 1) { 
            fprintf(stderr, "invalid input\n");
            return 1;
        }
        if((num < 0) || (num > length)) {
            fprintf(stderr, "invalid number %d\n", num);
            return 2;
        }

        goal=goal+i-num;
    };
    // printf("missing number: ");
    printf("%d\n", goal);
    return 0;
}

0 commentaires