Как найти пропущенный номер без использования массивов? - PullRequest
Новая
       47

Как найти пропущенный номер без использования массивов?

0 голосов
/ 24 сентября 2019

Я должен найти пропущенное число в последовательности чисел.Входные данные состоят из положительного целого числа n от 0 до 35000 и n уникальных чисел с диапазоном [0..n].(Таким образом, этот диапазон содержит n + 1 число).

Я уже пробовал некоторые вещи с sum={n*(n+1)}/2, а затем misNum=sum-SumOfNum;, но я не смог найти способ заставить эту работу.

Я написал некоторый код, но не с примерами, которые я упоминал ранее.Очевидно, что этот код не завершен, но я не знаю, как его завершить. 

#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;
}

Входные данные и результат должны быть:

Ввод: 2 "enter" 0 2.Выход: 1

Вход: 3 "ввода" 0 3 1. Выход: 2

Ответы [ 3 ]

3 голосов
/ 24 сентября 2019

Сумма всех чисел от 0 до n равна

n (a1 + an) / 2 = (в вашем случае a1 = 0 и an = n + 1) n * (n + 1) / 2

, поэтому отсутствующее число равно n * (n + 1) / 2 - (сумма входных чисел после длины) 

#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);
}
1 голос
/ 24 сентября 2019

У вас есть n количество целых чисел для сканирования.Используйте математическое уравнение для вычисления суммы первых n+1 натуральных чисел .Затем выполните цикл для n раз, а затем выполните цикл для добавления всех отсканированных n чисел.Затем вычтите эту сумму с суммой n+1 натурального числа.Результатом будет отсутствующий номер.

0 голосов
/ 24 сентября 2019

Расчет из вопроса также является правильным и может быть сделан для работы с несколькими модификациями. 

#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;
}
...