[C] Algoritmo numeri semi-perfetti

[FatBeats]

Inizio subito col dirvi, per chi non lo sapesse, che un numero N si dice semi-perfetto quando la somma di alcuni (o tutti) i suoi divisori è uguale al valore del numero N.

la prima cosa banale da fare è trovare tutti i divisori e memorizzarli in un vettore.
dopo di che viene il "difficile" almeno per quanto mi riguarda...ovvero non riesco a combinare qualche ciclo in modo tale da provare a sommare tutte le combinazioni dei divisori trovati.

sapete aiutarmi??



ESEMPIO:
nel caso del numero 12, i suoi divisori sono: 1, 2, 3, 4, 6.
il numero 12 è un numero semi-perfetto dato che 1 + 2 + 3 + 6 = 12.

[andbin]

Vediamo se ti dice qualcosa il sistema di numerazione binario:

1  2  3  4  6  | somma
---------------+------
0  0  0  0  0  |  0
0  0  0  0  1  |  6
0  0  0  1  0  |  4
0  0  0  1  1  |  10
0  0  1  0  0  |  3
0  0  1  0  1  |  9
....
....

[FatBeats]

mi dice qualcosa si....ma non riesco a combinare i cicli per creare tutte le combinazioni....

forse mi sto perdendo in un bicchiere d'acqua :master:

[oregon]

Ma il codice che trova i divisori e li inserisce nel vettore, lo hai scritto?

[FatBeats]

certo...

int numeriSemiperfetti (int);

int main (){
int n;
scanf ("%d", &n);
numeriSemiperfetti (n);
system ("PAUSE");
}

int numeriSemiperfetti (int n){
int i, y, j=0, somma=0, vett[100];
for (i=1; i<n; i++){
if (n % i == 0) {
vett[j]=i;
printf ("%d ", vett[j]);
j++;
}
}
}

[andbin]

Originariamente inviato da FatBeats
mi dice qualcosa si....ma non riesco a combinare i cicli per creare tutte le combinazioni....

forse mi sto perdendo in un bicchiere d'acqua :master:

A dire il vero non devi determinare le combinazioni con dei cicli for annidati, in quanto il numero di divisori è variabile e non noto a priori. Se il numero fosse fisso, allora certo che potresti fare dei cicli annidati.

Dati N divisori, devi generare 2^N combinazioni secondo la numerazione binaria. La soluzione più generica è quella di avere un array ad es. di N char in cui ognuno vale 0 o 1. Passare da una combinazione alla successiva è facile se aggiungi 1 alla combinazione facendo fare il "riporto" del carry dalla cifra meno significativa a quella più significativa.

[FatBeats]

pensavo di ricavarmi la lunghezza del vettore con sizeof ma evidentemente sbagliavo...

comunque ho capito cosa intendi...ma non riesco a riportarlo in codice

[andbin]

La generazione delle combinazioni binarie io la farei così (qui ho messo 4 bit fissi ma in teoria possono essere N):

Prova questo programmino:

#include <stdio.h>

int main (void)
{
    char bin[4] = { 0, 0, 0, 0 };
    char carry;
    int  i;

    do {
        for (i = 0; i < 4; i++)
            printf ("%d ", bin[i]);
        printf ("\n");


        carry = 1;

        for (i = 3; i >= 0; i--)
        {
            bin[i] += carry;
            if (bin[i] > 1)
                bin[i] = 0;
            else
            {
                carry = 0;
                break;
            }
        }
    } while (carry == 0);

    return 0;
}

[FatBeats]

grazie....ho seguito il tuo consiglio e ci sono riuscito.

praticamente la "somma" di ogni combinazione l'ho ricavata moltiplicando i valori contenuti negli indici che andavano da 0 a N-1 (N = numero di divisori, quindi numero di 0 e 1) dei 2 vettori presenti, fra di loro (il primo vettore con i divisori, il secondo con la combinazione in binario).

ovviamente se in almeno una combinazione la somma era uguale al numero esaminato...si ha un numero semi-perfetto.



..ancora grazie.

[andbin]

Originariamente inviato da FatBeats
l'ho ricavata moltiplicando i valori contenuti negli indici che andavano da 0 a N-1

Moltiplicazione???? Ma no ... basta un semplice test: se bit == 1 allora somma divisore corrispondente.