Özündən başqa massiv hasil#937

Özündən başqa massiv hasil (Həll təhlili)

Tutaq ki, $in$ — giriş massivi, indeksləşdirməni $1$ -dən başlayaq. Beləliklə, girişdəki ədədlər $in [1], in [2], ..., in [n]$ in[1], in[2], ..., in[n] yerlərdə saxlanılır. Əgər $in$ massivinin bütün elementlərinin hasilini $p$ hesablayıb, sonra isə $o u t_{i} = p / i n_{i}$ out_i = p / in_i ( $o u t$ — nəticə massivi) təyin etsək, bu metod $i n_{i} = 0$ in_i = 0 olduğu halda işləmir.

Başqa yanaşmanı nəzərdən keçirək. İki massiv quraq:

Prefiks hasil massiv $p r e f$ , burada

p r e f [i] = in [1] \cdot in [2] \cdot ... \cdot in [i],

pref[i] = in[1] \cdot in[2] \cdot ... \cdot in[i],

burada $p r e f [0] = 1$ pref[0] = 1 qoyaq;

Suffix hasil massiv $s u f$ , burada

s u f [i] = in [i] \cdot in [i + 1] \cdot ... \cdot in [n],

suf[i] = in[i] \cdot in[i + 1] \cdot ... \cdot in[n],

burada $s u f [n + 1] = 1$ suf[n + 1] = 1 qoyaq;

Beləliklə, $o u t_{i} = p r e f [i - 1] \cdot s u f [i + 1]$ out_i = pref[i - 1] \cdot suf[i + 1].

Nümunə

Alqoritmin reallaşması

İşçi massivi elan edək.

#define MAX 1000002
int in[MAX], pref[MAX], suf[MAX], res[MAX];

Giriş məlumatlarını oxuyaq.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%d",&in[i]); // [1,2,3,4]

Prefiks hasil massivini quraq.

pref[0] = 1;
for(i = 1; i <= n; i++) // [1,2,6,24]
  pref[i] = pref[i-1] * in[i];

Suffix hasil massivini quraq.

suf[n+1] = 1;
for(i = n; i >= 1; i--) // [24,24,12,4]
  suf[i] = suf[i+1] * in[i];

Nəticə massivini quraq.

for(i = 1; i <= n; i++)  // [24,12,8,6]
  res[i] = pref[i-1] * suf[i+1];

Cavabı çap edək.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");