Блог

Программа получает массив целых чисел. Необходимо в каждой новой строке выводить сумму i-го элемента массива. Например, для такого массива {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ответ будет таким :

 55 //1 2 3 4 5 6 7 8 9 10
30 //2 4 6 8 10
18 //3 6 9
12 //4 8
15 //5 10
6  //6
7  //7
8  //8
9  //9
10 //10
  

Вот мой код, который решает эту проблему:

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

int main(void) { 
    int N, i, j, S; 
    scanf("%d",amp;N); //length of array
    int a[N];
    for(i = 0; i < N;   i) scanf("%d",amp;a[i]); 
    for(i = 1; i <= N;   i) {
        S = 0;
        for(j = 0; j < N;   j) 
            S  = !((j 1)%i) ? a[j] : 0; 
        printf("%dn",S);
    }
    return 0;
}
  

Моя проблема в том, что мой алгоритм недостаточно быстр. А на больших данных его скорость очень низкая.
Я попытался придумать алгоритм, который бы рекурсивно вычислял сначала небольшие суммы, а затем вычислял другие. Но мне не удалось это реализовать.

Пожалуйста, не могли бы вы дать мне более элегантный вариант решения этой проблемы.

Простая модификация помогает избежать проверки всех индексов:

 for(j = i - 1; j < N; j  = i) 
        S  = a[j]; 
  

for Цикл не должен увеличивать переменную итератора только на единицу, вы можете добавить к ней любую сумму, например a[i - 1] , как в:

 for(j = 0; j < N; j  = a[i - 1])
  

Это означает, что самый внутренний цикл не будет выполняться столько раз в последующих итерациях.

Это также означает, что вы можете просто пропустить условие внутри самого внутреннего цикла и просто выполнить

 S  = a[j];
  

Примечание: это не проверено и может потребовать некоторой настройки. Общий принцип — важная часть: делай меньше!