Em relação ao exemplo com 3 4 6 0 2 9 está claro que 6 0 2 somam 8 e está ok, a soma de todos os números dá 24 então esta é a segunda solução.
Uma terceira solução é o 0 por si só, como seria o caso de qualquer múltiplo de 8 num quadrado. (@Kiritonito me apontou isso)
Uma notação geral
Uma solução possível pode ser escrita como um par (i,j)
com o início em i
e o comprimento j
da sequência.
Para 8 0 8 0 8
temos
0, 1 0, 2 0, 3 0, 4 0, 5
1, 1 1, 2 1, 3 1, 4 2, 1
2, 2 2, 3 3, 1 3, 2 4, 1
As 15
soluções.
Caso particular
- Com todos os quadrados com multiplos de 8 o total de soluções deve ser
(N+1)*N / 2
, e 10 quadrados com 8 devem levar a 55 soluções
Um exemplo em C
Alterei um pouco o programa original para gravar em arquivo q8.txt as soluções encontradas, assim se pode conferir o programa e ver os "quadrados" encontrados.
#define LIMITE_ (1000 * 1000)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char** argv)
{
const char* s_padrao = "q8.txt"; // entrada padrao
unsigned limite = LIMITE_; // limite padrao
char arquivo_s[80];
char na_tela = 0;
char linha[256];
if (argc > 1)
strcpy(arquivo_s, argv[1]);
else
strcpy(arquivo_s, s_padrao);
//fprintf(stderr, "Saida em \"%s\"\n", arquivo_s);
FILE* S = fopen(arquivo_s, "a");
if (S == 0) return -1; // nao abriu saida
unsigned N;
int res = scanf("%d", &N);
fgets(linha, 256, stdin); // le o resto da linha
if (res != 1) return -2;
if (N > LIMITE_) N = LIMITE_;
fprintf(S,"%d numeros\n", N);
short* V = (short*)malloc(sizeof(short) * N);
if (V == NULL) return -3;
// le os numeros ate preencher o vetor inicial
for (unsigned i = 0; i < N; i += 1)
{
res = scanf("%hd", (V+i) );
if (res != 1)
return -4;
else
fprintf(S, "%6d", *(V + i));
}
fprintf(S, "\n");
// busca as solucoes
unsigned total = 0;
for (unsigned i = 0; i < N; i += 1)
{
if (*(V+i) % 8 == 0)
{
fprintf(S, "%d, 1\n", i);
total += 1;
}
unsigned soma = *(V+i); // o primeiro, claro
for (unsigned j = i+1; j < N; j += 1)
{
soma += *(V + j);
if ((soma % 8) == 0)
{
fprintf(S, "%d, %d\n", i, 1+j-i);
total += 1;
};
}
}
fprintf(S, "Total: %d solucoes\n\n", total);
fclose(S);
printf("%d\n", total);
free(V);
return 0;
}; // main()
Saída em q8.txt (exemplos)
Esse é o arquivo gerado
6 numeros
3 4 6 0 2 9
0, 6
2, 3
3, 1
Total: 3 solucoes
7 numeros
1 1 1 1 1 1 1
Total: 0 solucoes
5 numeros
8 0 8 0 8
0, 1
0, 2
0, 3
0, 4
0, 5
1, 1
1, 2
1, 3
1, 4
2, 1
2, 2
2, 3
3, 1
3, 2
4, 1
Total: 15 solucoes
4 numeros
0 0 0 0
0, 1
0, 2
0, 3
0, 4
1, 1
1, 2
1, 3
2, 1
2, 2
3, 1
Total: 10 solucoes
4 numeros
8 16 24 32
0, 1
0, 2
0, 3
0, 4
1, 1
1, 2
1, 3
2, 1
2, 2
3, 1
Total: 10 solucoes
saida no terminal
6
3 4 6 0 2 9
3
7
1 1 1 1
1 1 1
0
5
8 0 8 0 8
15
De volta ao programa original
if (n <= 0 || n > 1000000) printf("valor invalido!\n\n informe outro:\n");
} while (n < 0 || n > 1000000);
int numeros[n];
for (i = 0; i < n; i++) {
do {
printf("informe os numeros(de 1 a 1000): ");
scanf("%d", & numeros[i]);
if ((numeros[i] < 0 || numeros[i] > 1000)) printf("valor invalido!\n\n informe outro:\n");
} while (numeros[i] < 0 || numeros[i] > 1000);`
Sugestões
- declare variáveis de controle do
for
no próprio comando
- ao usar
do/while
evite construções como essa em que testa duas vezes a mesma coisa
main()
retorna int.
- declare vetores de dimensão constante ou use malloc() e crie o vetor na hora.