Esercizio in C

[zavo91]

ho un esercizio che mi dice:
si scriva un funzione p(int n,int m) che, presi in ingresso due numeri n ed m,ritorni 1 se n è divisibile per una qualsiasi potenza $m^i$ di m, con i>1, e 0 altrimenti...

#include<stdio.h>
#include<math.h>
int p(int n,int m)
{
	int i,a;
	for(i=2;i<=m;i++)
	{
		while(m>0)
		{
			m=m^i;
			a=n%m;	
			if(a!=0)
				return 1;
		}
	return 0;
		
	}
}
int main ()
{
	printf("%i\n",p(8,4));
	
}

però non funziona e non capisco dove sbaglio...

[vict85]

Per prima cosa m^i non ha come risultato $m^i$, l'operatore ^ in c ha come significato l'operatore or esclusivo. Cioé una operazione bit a bit (http://digilander.libero.it/uzappi/C/C-operatori.html). Per le potenze devi moltiplicare semplicemente per lo stesso valore (puoi anche usare pow ma in questo caso è inutile).

Se i è maggiore strettamente di 1 allora ti basta testare per i = 2, anche perché non devi far tornare il massimo i per cui questo vale.

[zavo91]

non mi è chiaro come devo moltiplicare m per lo stesso valore...intendi dire dove io ho scritto m^i devo scrivere m*m ma come faccio a dirgli di moltiplicare m per se stesso i volte??? come lo modificheresti te il testo?

[vict85]

"zavo91":non mi è chiaro come devo moltiplicare m per lo stesso valore...intendi dire dove io ho scritto m^i devo scrivere m*m ma come faccio a dirgli di moltiplicare m per se stesso i volte??? come lo modificheresti te il testo?

Il tuo codice fa calcoli inutili infatti \(\displaystyle m^i\mid n \Leftrightarrow m\mid n \) dove segno con \(\displaystyle m\mid n \) che \(\displaystyle m \) divide \(\displaystyle n \). Similmente se richiedi che i>1 allora ti basta testare la divisibilità per \(\displaystyle m^2 \).

Quindi rimarrebbe qualcosa di questo tipo:

int p(int m, int n)
{
   int resto = n%(m*m);
   int val_rit = (rest == 0);
   return val_rit;
}

oppure se i può essere uguale a 1:

int p(int m, int n)
{
   int resto = n%m;
   int val_rit = (rest == 0);
   return val_rit;
}

Ovviamente il tutto può essere scritto in una sola riga e puoi assegnare val_rit con un if oppure con un operatore ternario. Con l'if diventerebbe:

int p(int m, int n)
{
   int resto = n%(m*m);
   int val_rit;
   if(rest == 0)
   {
      val_rit = 1;
   }
   else
   {
      val_rit = 0;
   }
   return val_rit;
}

Dovrebbero funzionare tutti bene. Ma potrei aver fatto qualche errore di disattenzione/battitura.

In ogni caso per una potenza si può usare un semplice for:

int prod = 1;
for(int j = 0; j < i; j++)
{
   prod*=m;
}

oppure anche:

 for(int j = 0, int prod = 1; j < i; j++, prod*=m);

Ma forse un po' ne lede la leggibilità.

La funzione pow usa i double quindi il risultato potrebbe non essere molto preciso. C'é inoltre un metodo soprannominato "fast exponentiation" per ridurre molto il numero di moltiplicazioni. Ti suggerisco di dargli un occhiata anche solo per entrare un po' di più nella mentalità informatica.

P.S: per la potenza di due c'é un metodo più rapido, ma è meglio se lo eviti per ora. Soprattutto sugli int, è più "affidabile" sugli unsigned.

P.S2: qui trovi qualcosa sulla fast exponention http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[zavo91]

cioè quello che chiede il mio testo dell'esercizio bastava farlo in 3 righe??
cavolo sono messo male allora...
P.S.1 ma perchè vai a vedere solo $m^2$ e non ad esempio $m^19$?? perchè è una questione della matematica come hai scritto ad inizio spiegazione quella che dice \(\displaystyle m^i\mid n \Leftrightarrow m\mid n \) dove segno con \(\displaystyle m\mid n \) che \(\displaystyle m \) divide \(\displaystyle n \). Similmente se richiedi che i>1 allora ti basta testare la divisibilità per \(\displaystyle m^2 \).???
P.S.2 come posso fare per entrare un pò di più nella logica dell'informatica di programmazione?

[vict85]

Se tu hai un numero, per esempio 10 allora un numero divisibile per 10000 è anche divisibile per 10, per il semplice fatto che 10000 è divisibile per 10. Nello stesso modo se tu vuoi che sia divisibile per una potenza maggiore di uno allora testare solo per 10 non va bene perché tu cerchi i multipli di 100. In effetti il se e solo se era sbagliato, l'implicazione è in un solo senso.

Un altra cosa è se invece devi cercare la potenza massima per cui \(\displaystyle m^i\mid n \). In quel caso il programma diventava qualcosa di questo tipo:

int funzione(int m, int n)
{
  int prod = m, i = 0;
  for(; n%prod == 0; i++)
  {
    prod = prod * m;
  }
  return i;
}

Attento però che invece

int funzione(int m, int n)
{
  int prod = m;
  for(int i = 0; n%prod == 0; i++)
  {
    prod = prod * m;
  }
  return i;
}

non compila! Perché in questo caso i esiste solo all'interno del for.

Riguardo alla programmazione direi che si tratta principalmente di ragionare sul problema e di dividerlo in sottoproblemi. Cioé devi cercare di capire cosa esattamente deve fare la funzione. Comunque è essenziale sapere cosa esattamente puoi fare, il tuo problema iniziale era fondamentalmente il pensare che esistesse un operatore per fare l'esponenziazione. In parte il vedere tanti programmi aiuta.