aiuto matematico

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

credo sia equivalente a 7x+ 20y+3z-200=0
Sì, hai ragione, il problema può essere ricondotto a coefficienti interi, c'è solo, è ovvio, un incremento di soluzioni, come mostro sotto. Appena riuscirai a far quadrare i MCD, con lo script in C potrai ottenere anche tu le soluzioni multiple, adottando un opportuno ciclo che ne scandagli le variazioni. Continuerò sempre a seguirti. Ciao
Spoiler
Mostra

Codice: Seleziona tutto

 Valore iniziale intero delle 3 incognite [try 200]: 200

 Equazione data: 7 * x +  20 * y +  3 * z -  200  = 0

 Soluzione: (x,y,z)=  24 1 4
 Soluzione: (x,y,z)=  22 2 2
 Soluzione: (x,y,z)=  21 1 11
 Soluzione: (x,y,z)=  19 2 9
 Soluzione: (x,y,z)=  18 1 18
 Soluzione: (x,y,z)=  17 3 7
 Soluzione: (x,y,z)=  16 2 16
 Soluzione: (x,y,z)=  15 4 5
 Soluzione: (x,y,z)=  15 1 25
 Soluzione: (x,y,z)=  14 3 14
 Soluzione: (x,y,z)=  13 5 3
 Soluzione: (x,y,z)=  13 2 23
 Soluzione: (x,y,z)=  12 4 12
 Soluzione: (x,y,z)=  12 1 32
 Soluzione: (x,y,z)=  11 6 1
 Soluzione: (x,y,z)=  11 6 1
 Soluzione: (x,y,z)=  11 3 21
 Soluzione: (x,y,z)=  10 5 10
 Soluzione: (x,y,z)=  10 2 30
 Soluzione: (x,y,z)=  9 4 19
 Soluzione: (x,y,z)=  9 1 39
 Soluzione: (x,y,z)=  8 6 8
 Soluzione: (x,y,z)=  8 3 28
 Soluzione: (x,y,z)=  7 5 17
 Soluzione: (x,y,z)=  7 2 37
 Soluzione: (x,y,z)=  6 7 6
 Soluzione: (x,y,z)=  6 4 26
 Soluzione: (x,y,z)=  6 1 46
 Soluzione: (x,y,z)=  5 6 15
 Soluzione: (x,y,z)=  5 3 35
 Soluzione: (x,y,z)=  4 8 4
 Soluzione: (x,y,z)=  4 5 24
 Soluzione: (x,y,z)=  4 2 44
 Soluzione: (x,y,z)=  3 7 13
 Soluzione: (x,y,z)=  3 4 33
 Soluzione: (x,y,z)=  3 1 53
 Soluzione: (x,y,z)=  2 9 2
 Soluzione: (x,y,z)=  2 6 22
 Soluzione: (x,y,z)=  2 3 42
 Soluzione: (x,y,z)=  1 8 11
 Soluzione: (x,y,z)=  1 5 31
 Soluzione: (x,y,z)=  1 2 51

 -------- Fine della scansione --------
.
------- Fine calcolo -----------

C:\Training>
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

E' necessario conoscere una soluzione particolare dell'equazione diafantea del post d'apertura, per risolverla con il metodo di Eulero.
Per dimostrare tale affermazione vado step-by-step, lasciandomi guidare dal menzionato libro in PDF di Luigi Verolino, pagg. 46-47: equazioni diofantee lineari a 3 variabili.

Codice: Seleziona tutto

         La nostra equazione è: 33*x + 50*y + 75*z = 233   [1]
         
         Massimo comune divisore MCD(33,50,75)=1, quindi bisogna
         risolvere l'equazione omogenea: 33*x0 + 50*y0 + 75*z0 = 0
                  
         Poniamo y0=3*k -> 33*x0 + 50*3*k + 75*z0 = 0, da cui, 
                           semplificando, otteniamo: 11*x0 + 25*z0= -50*k
         Altra posizione:  x0=25*h, da cui 11*25*h+25*z0 = -50*k,
                           ovvero: z0= -2*k - 11*h
                           
         Riepilogando:  x0= 25*h;  y0= 3*k;   z0= -2*k - 11*h 
                        (soluzione dell'equazione omogenea)
         
         Manca ancora una soluzione particolare dell'equazione completa,
         nel nostro caso {xp=1; yp=1; zp=2}, che risolve la [1], per
         cui la soluzione dell'equazione completa diventa:
         
                x= 25*h + 1;  y= 3*k + 1;   z= -2*k - 11*h + 2                                     
                            
                 (identica a quella di figura, con n1=h e n2=k)

Ne deriva che il procedimento,condizionato dalla conoscenza di almeno una soluzione (particolare) dell'equazione data, entra in un vicolo cieco e necessariamente si blocca. E ad essa si arriva, questa è la mia opinione, utilizzando il metodo ciclico che ho esposto nei post precedenti, da inglobare in quello di Eulero.

Ciao
Allegati
diofantea-a-3-variabili.png
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Non ti seguo molto...forse già dimentico ciò che ho "studiato" :D
Nel mio programma, tramite i coefficienti di Bezout calcolo la soluzione particolare, da li poi trovo le varie soluzioni.
Solo che al momento non so come adattare il tutto a 3 o più incognite.
A dire il vero in questi giorni non ci ho messo mano.
75x+33y=99
diventa 25x+11y=33

mcd tra 25 e 11=1
identità di bezout tra 25 e 11 = 4,-9
quindi soluzione base:
25*4+11*-9=1
ma anche 25*15+11*-34=1
oppure
25*-7+11*16=1
Appena posso provo il tuo script, anche se non ho ben capito come si comporta nel caso non esistano soluzioni positive:
es 75x+50y+33z=157
EDIT a quanto pare da sopra, te ne intendi e mastichi meglio la matematica di me :)
Calcola che io non ho studi in merito...quel poco che ho fatto nel programma sopra è solo frutto di hobby e un po' d'impegno.
E quel poco che ho fatto risale almeno a quasi 30 anni fa.
PS: se hai tempo, trasformi il codice python in C? Non so nulla di python.
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

... anche se non ho ben capito come si comporta nel caso non esistano soluzioni positive:
es 75x+50y+33z=157
Basta estendere l'intervallo di scansione a valori negativi, nell'esempio: N2=-20, mentre N1=20 è il valore di inizio dei cicli a "scendere".
Spoiler
Mostra

Codice: Seleziona tutto

         ------------ Equazione --------------
            33*x + 50*y + 75*z = 157
         -------------------------------------
 (x,y,z)=  4 20 -13
 (x,y,z)=  4 17 -11
 (x,y,z)=  4 14 -9
 (x,y,z)=  4 11 -7
 (x,y,z)=  4  8 -5
 (x,y,z)=  4  5 -3
 (x,y,z)=  4  2 -1
 (x,y,z)=  4 -1  1
 (x,y,z)=  4 -4  3
 (x,y,z)=  4 -7  5
 (x,y,z)=  4 -10  7
 (x,y,z)=  4 -13  9
 (x,y,z)=  4 -16 11
 (x,y,z)=  4 -19 13
 
/* (diof3.c) diofantea a 3 variabili ------ 22.Mag.17 -------- 
 *  per risolvere un'equazione del tipo 
 *   a*x + b*y + c*z = d  [(a,b,c,d) numeri interi POSITIVI e MAGGIORI di 0, 
 *                          altrimenti l'equazione non sarebbe piu' a 3 variabili
 *                         e (x,y,z) numeri interi qualsiasi]
 */
#include <stdio.h>
#include <stdlib.h>
#define N1 20 /* Valore massimo (x,y,z) intervallo di scansione*/
#define N2 -20 /* Valore minimo (x,y,z) intervallo di scansione*/

int main(void)
{   
	int a,b,c,d, somma, i,j,k;
	
/* ----------- Coefficienti e termine noto dell'equazione diafontea ---------- */
	a= 33;       
	b= 50;       
	c= 75;       
	d= 157;
//	 ------------------------------------------ ------------------------------
	printf("\n\t ------------ Equazione -------------- ");
	printf("\n\t    %d*x + %d*y + %d*z = %d", a,b,c,d);
	printf("\n\t -------------------------------------\n");

    j=N1; k=N1;

// ------------ Inizio 3 cicli nidificati -------------------------
	for (i=N1;i>N2;i--){
		somma= a*i + b*j + c*k -d;
		if (somma==0) { printf (" (x,y,z)= %2d %2d %2d \n", i,j,k); }
			for (j=N1;j>N2;j--){
		    somma= a*i + b*j + c*k -d;
		    if (somma==0) { printf (" (x,y,z)= %2d %2d %2d \n", i,j,k); }		
		    	for (k=N1;k>N2;k--){
				somma= a*i + b*j + c*k -d;
				if (somma==0) { printf (" (x,y,z)= %2d %2d %2d \n", i,j,k); }			
    			} 
			}
	} 

printf ("\n\t\t Fine della scansione \n");

    return 0;
}
 
Buon divertimento con diof3.c. Ciao
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Onestamente mi sono buttato subito nella risoluzione "rigorosa" è non ci ho nemmeno provato col brute force.
Ma devo dire che non so se ci sarei arrivato. Naturalmente i "puristi" matematici storcerebbero il naso, ma ad ogni
modo bravo! Non ho ancora provato, il tempo è quello che è. Certo che però mi salvo il codice.
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

Grazie del feedback, Gila!
Per adesso accontentiamoci della "brutalità" della soluzione, che comunque porta ad avere delle soluzioni immediatamente disponibili, ma mi aspetto che tu continui con la tua ricerca per migliorare l'attuale algoritmo. Proseguiremo con il C, naturalmente. Ciao
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Spero di aver tempo...con 2 incognite e un po' di aiuto sono riuscito a capire...con 3 sembra che la "solfa" si complichi.
Sicuramente alcuni utenti, magari le nuove leve lo sanno fare, ma gli è che so' pigri :D :D
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

Miglioramento della scansione, tramite i valori massimi di (x,y,z), che si ottengono quando i minimi sono unitari, così:

Codice: Seleziona tutto

    xmax= (d-b-c)/ (float) a; /* quando y=1 e z=1 */
    ymax= (d-a-c)/ (float) b; /* quando x=1 e z=1 */
    zmax= (d-a-b)/ (float) c; /* quando x=1 e y=1 */
Con questo adattamento finisce l'aspetto "brute force" del metodo di calcolo che ho proposto, in quanto si conoscono gli intervalli di variazione delle 3 incognite, e tutte le soluzioni dell'equazione a 3 variabili vengono calcolate univocamente. Chiudo qui il mio intervento al thread e ringrazio.
Sotto, codice in C + output
Spoiler
Mostra

Codice: Seleziona tutto

/* (diof3B.c) diofantea a 3 variabili ------ 23.Mag.17 -------- 
 *  per risolvere un'equazione del tipo 
 *   a*x + b*y + c*z = d  [(a,b,c,d) e (x,y,z) numeri interi POSITIVI e MAGGIORI di 0]
 */
#include <stdio.h>
#include <stdlib.h>

int main(void)
{   
	int a,b,c,d, somma, i,j,k, xmax,ymax,zmax;
	
/* ----------- Coefficienti e termine noto dell'equazione diafontea ---------- */
	a= 7;       
	b= 20;       
	c= 3;       
	d= 200;
//	 ------------------------------------------ ------------------------------
	printf("\n\t ------------ Equazione -------------- ");
	printf("\n\t    %d*x + %d*y + %d*z = %d", a,b,c,d);
	printf("\n\t -------------------------------------\n");

    xmax= (d-b-c)/ (float) a; /* quando y=1 e z=1 */
    ymax= (d-a-c)/ (float) b; /* quando x=1 e z=1 */
    zmax= (d-a-b)/ (float) c; /* quando x=1 e y=1 */

    printf ("\n (xmax,ymax,zmax)= %2d %2d %2d \n\n", xmax,ymax,zmax);
    
    j=ymax; k=zmax;
    

// ------------ Inizio 3 cicli nidificati -------------------------
	for (i=1;i<xmax;i++){
		somma= a*i + b*j + c*k -d;
		if (somma==0) { printf (" (x,y,z)= %2d %2d %2d \n", i,j,k); }
			for (j=1;j<ymax;j++){
		    somma= a*i + b*j + c*k -d;
		    if (somma==0) { printf (" (x,y,z)= %2d %2d %2d \n", i,j,k); }		
		    	for (k=1;k<zmax;k++){
				somma= a*i + b*j + c*k -d;
				if (somma==0) { printf (" (x,y,z)= %2d %2d %2d \n", i,j,k); }			
    			} 
			} 
	} 

printf ("\n\t\t Fine della scansione \n");

    return (EXIT_SUCCESS);
}
/*
          ------------ Equazione --------------
            7*x + 20*y + 3*z = 200
         -------------------------------------

 (xmax,ymax,zmax)= 25  9 57

 (x,y,z)=  1  2 51
 (x,y,z)=  1  5 31
 (x,y,z)=  1  8 11
 (x,y,z)=  2  3 42
 (x,y,z)=  2  6 22
 (x,y,z)=  3  1 53
 (x,y,z)=  3  4 33
 (x,y,z)=  3  7 13
 (x,y,z)=  4  2 44
 (x,y,z)=  4  5 24
 (x,y,z)=  4  8  4
 (x,y,z)=  5  3 35
 (x,y,z)=  5  6 15
 (x,y,z)=  6  1 46
 (x,y,z)=  6  4 26
 (x,y,z)=  6  7  6
 (x,y,z)=  7  2 37
 (x,y,z)=  7  5 17
 (x,y,z)=  8  3 28
 (x,y,z)=  8  6  8
 (x,y,z)=  9  1 39
 (x,y,z)=  9  4 19
 (x,y,z)= 10  2 30
 (x,y,z)= 10  5 10
 (x,y,z)= 11  3 21
 (x,y,z)= 11  6  1
 (x,y,z)= 12  1 32
 (x,y,z)= 12  4 12
 (x,y,z)= 13  2 23
 (x,y,z)= 13  5  3
 (x,y,z)= 14  3 14
 (x,y,z)= 15  1 25
 (x,y,z)= 15  4  5
 (x,y,z)= 16  2 16
 (x,y,z)= 17  3  7
 (x,y,z)= 18  1 18
 (x,y,z)= 19  2  9
 (x,y,z)= 21  1 11
 (x,y,z)= 22  2  2
 (x,y,z)= 24  1  4

                 Fine della scansione
*/



gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

molto bene..a conti fatti mi sono andato a incasinare parecchio!!
Forse sono stato precipitoso a buttarmi sulla risoluzione matematica. Comunque come detto (tempo permettendo)
posterò il seguito... se ci sarà ;)
Avatar utente
Dclaudio1990
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 624
Iscrizione: sabato 11 aprile 2015, 14:31
Distribuzione: openSUSE
Sesso: Maschile
Località: Roma

Re: aiuto matematico

Messaggio da Dclaudio1990 »

Salve,
@gila se hai trovato la soluzione per le diofantee a 2 incognite, penso sia fattibile ridurre (in questo caso particolare) le diofantee con numero di incognite maggiore di 2, ad una equazione a due incognite:

ax+by+cz=k

ax+by=k-cz

Basta risolvere queste equazioni , partendo da z=1 finchè k-cz>a+b, incrementando di uno z.
Ovviamente la risoluzione avviene tramite la procedura rigorosa.
"Io penso, dunque sono, ossia esisto."
-René Descartes
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Ciao Dclaudio :)
Si le diofantee con 2 incognite le ho risolte, trovando i coefficienti di Bezout.
Con 3 o più variabili, non so bene come procedere. A dire il vero, causa tempo, non ho più messo mano.
Magari domani ho tempo.
Se hai voglia, spiegati un po' più nel dettaglio.
Nel caso grazie
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Quello che non capisco è come applicare i termini di Bezout a più elementi oltre a due.
Esempio ho:
75x+33y=33 semplifico e ho 25x+11y=11
l'mcd è 1 (25,11)
ora a conti fatti i termini sono 4,-9
infatti
25*4+11*-9=1
Ora come posso fare per trovare quei coefficienti che moltiplicati tra loro mi diano sempre l'mcd?
Intendo con 3 o più numeri?
è questo che mi sfugge e non trovo sui testi.
Il problema è stato risolto da BluEyes, ma voglio capire la "rigida" procedura matematica.
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

Ciao Gila. Più su tu scrivi:
Sì, le diofantee con 2 incognite le ho risolte, trovando i coefficienti di Bezout.
e sarei curioso di conoscere come faresti con la diofantea a 2 variabili della figura. Per comodità la riporto sotto, mostrandoti la mia soluzione

Codice: Seleziona tutto

             324*x + 81*y = 26   (x,y)>0 e interi
             
             Valori minimi di (x,y) uguali a 1
             324+81 diverso e maggiore di 26 (nessuna soluzione)
             A maggior ragione per valori superiori di (x,y)
Buon divertimento
Allegati
diof2.png
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

e sarei curioso di conoscere come faresti con la diofantea a 2 variabili della figura. Per comodità la riporto sotto, mostrandoti la mia soluzione
Non la posso fare essendo frazionaria, o meglio per il problema nato come imbottigliamento, la ignoro ,e tento soluzioni minori finchè è possibile
poi leggo l'eventuale scarto:
324*x + 81*y = 26

output:

Codice: Seleziona tutto

gila@gila-pc:~/Scrivania$ ./xx
cl 26: impossibile frazionario
cl 25: impossibile frazionario
cl 24: impossibile frazionario
cl 23: impossibile frazionario
cl 22: impossibile frazionario
cl 21: impossibile frazionario
cl 20: impossibile frazionario
cl 19: impossibile frazionario
cl 18: impossibile frazionario
cl 17: impossibile frazionario
cl 16: impossibile frazionario
cl 15: impossibile frazionario
cl 14: impossibile frazionario
cl 13: impossibile frazionario
cl 12: impossibile frazionario
cl 11: impossibile frazionario
cl 10: impossibile frazionario
cl 9: impossibile frazionario
cl 8: impossibile frazionario
cl 7: impossibile frazionario
cl 6: impossibile frazionario
cl 5: impossibile frazionario
cl 4: impossibile frazionario
cl 3: impossibile frazionario
cl 2: impossibile frazionario
cl 1: impossibile frazionario
x(324cl)=0 y(81cl)=0
LIQUIDO IMBOTTIGLIATO: cl 0
scarto: 26
324x+81y=2600 (anche questo sarebbe frazionario):
output:

Codice: Seleziona tutto

gila@gila-pc:~/Scrivania$ ./xx
cl 2600: impossibile frazionario
cl 2599: impossibile frazionario
cl 2598: impossibile frazionario
cl 2597: impossibile frazionario
cl 2596: impossibile frazionario
cl 2595: impossibile frazionario
cl 2594: impossibile frazionario
cl 2593: impossibile frazionario
x(324cl)=0 y(81cl)=32
LIQUIDO IMBOTTIGLIATO: cl 2592
scarto: 8
Come vedi, nel caso i risultati fossero frazionario o negativi arretro al primo risultato che mi da numeri interi, poi gestisco lo scarto.
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

Grazie, Gila, per la risposta.
La tua soluzione, però, è simile a quella grafica di figura, che riassumo così:

Codice: Seleziona tutto

        Poiché la retta dell'equazione data
        _non_ incrocia alcun punto della griglia
        unitaria (lati 1x1), allora _non_ c'è
        soluzione intera
Resto perplesso, credevo che tu avessi risolto la cosa con deduzioni matematiche (non empiriche, come mi sembra di capire)
usando il metodo che hai citato nei post precedenti [trovando i coefficienti di Bezout], a meno che quegli output non provengano da un programmino in C, dove tu li hai applicati. Ti ringrazio anticipatamente se pubblichi qui il relativo codice C.
Ciao, e sempre in gamba.
Allegati
retta.png
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Resto perplesso, credevo che tu avessi risolto la cosa con deduzioni matematiche (non empiriche, come mi sembra di capire)
Il problema iniziale era come imbottigliare tot liquido con x,y contenitori, quindi un risultato frazionario non lo devo considerare per il problema in questione.
Perchè modo empirico?
Se non posso "imbottigliare" ( risultati negativi e\o frazionari), logico che devo scalare di 1 cl, ma poi ripeto la procedura matematica.

Qui cercavo la soluzione del problema "imbottigliamento", dove risultati negativi e frazionari non servono, quindi alcune cose
rigorosamente matematiche non le ho approfondite (anche se sarebbe interessante, tempo permettendo)
La procedura adottata è matematica (per trovare x,y), solo che scalo di 1 cl finchè trovo una soluzione (se esite)
Dopo faccio un edit e metto il programma. Occhio che edit non da la notifica.
Se hai dubbi chiedi pure.

EDIT:
ecco questo è il codice:

Codice: Seleziona tutto

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



int mcd(int min,int max, int tab[][4],int *n);
void min_max (int *a,int *b);
void stampa (int n,int tab[][4]);
int bez (int n,int tab[][4],int liquido);
void init_array(int tab[][4],int a,int b);
void riduci(int *a,int *b, int *liquido,int mcd);
int test(int mcd, int *l, int *f, int copy_l,int *n);
int risolvi (int p,int a, int b,int liquido,int mcd,int copy_l);


//***********************************************
// scambia numeri per trovare il massimo dei 2
//***********************************************
void min_max (int *a,int *b)
{
	int temp;
	if (*a<*b)
	{
		temp=*a;
		*a=*b;
		*b=temp;
	}
}

//***********************************************
// trova MCD metodo di Eulero
//***********************************************
int mcd(int min, int max,int tab[][4],int *n)
{
	int r = 1;
	int res;
	
	if (min == 0)
    	return max;
    else
    	while (r > 0)
		{
       		r = max % min;
			res=max/min;
        	max = min;
        	min = r;
			tab[*n+1][0]=min;
			tab[*n][1]=res;
			*n=(*n)+1;
		}
	
	return max;
}

//***********************************************
// test: se il liquido non è un multiplo dei
// 2 membri (75,33 nel mio) caso
// il risultato sarà frazionario e a me non va bene
//*************************************************
int test(int mcd, int *l, int *f, int copy_l,int *n)
{
	if  ( (*l%mcd)!=0)
	{	
		printf("cl %d: impossibile frazionario\n",*l);
		*f=*f+1;
		*l=copy_l-*f;
		*n=0;
		return 0;
	}
		
	return 1;
	
}

void riduci(int *a,int *b, int *liquido,int mcd)
{
	
	if ( (*liquido%mcd)==0 )
	{
		*a=*a/mcd;
		*b=*b/mcd;
		*liquido=*liquido/mcd;
		
		
	}
}

//***********************************************
// preparo l'array per il calcolo
// dei coefficienti di Bezout
//***********************************************
void init_array(int tab[][4],int a,int b)
{
	int r,c;
	for (r=0; r<50; r++)
	{
		for (c=0; c<4; c++)
			tab[r][c]=0;
	}
		
	tab[0][0]=a;
	tab[1][0]=b;
	tab[0][2]=1;
	tab[1][3]=1;
}
//***********************************************
// calcolo identità p di Bezout
//***********************************************
int bez (int n,int tab[][4], int liquido)
{
	int i;
	for (i=0; i<n; i++)
	{
		tab[i+2][2]=tab[i][2]-(tab[i+1][1]*tab[i+1][2]);
	}
	
	return tab[n-1][2]*liquido;
}




//***********************************************
// eventuale stampa per vedere la matrice
// che mi permette di vedere i passaggi
// e le identità di B.
//***********************************************
void stampa (int n,int tab[][4])
{
	int r,c;
	for (r=0; r<n; r++)
	{
		for (c=0; c<4; c++)
		{
			printf ("%d ", tab[r][c]);
		}
		puts("");
	}
	puts("-------------------");
}

//***********************************************
// calcola prima x, poi y
//***********************************************
	
int risolvi (int p,int a,int b,int liquido,int mcd,int copy_l)
{
	int res,x,y;
	
	res=p/b;	
	x=p-(res*b);
	y=(liquido-(a*x))/b;
	printf ("Negativi: x=%d y=%d\n",x,y);
	if (x>=0 && y>=0)
	{
		printf ("x(324cl)=%d y(81cl)=%d\n",x,y);
		printf ("LIQUIDO IMBOTTIGLIATO: cl %d\n", (a*x+b*y)*mcd);
		printf ("scarto: %d\n", (copy_l-(a*x*mcd+b*y*mcd)));
		return 1;
	}
	return 0;
	
}

	


int main (void)
{
	int a=324; //x
	int b=81; //y
	int liquido=2600;
	int copy_l=liquido;
    int aa=a;
	int bb=b;
	int res,p,x,t;
	int tab[50][4];
	int n;
	int f=0;
	
	while (1)
	{
		while(1)
		{
			min_max(&a,&b); 
			init_array(tab,a,b);
			res=mcd(a,b,tab,&n);
			t=test(res,&liquido,&f,copy_l,&n);
			if (t==1)
				break;
		}
			
		riduci (&a,&b,&liquido,res);
		p=bez(n,tab,liquido);
		
			
		x=risolvi(p,a,b,liquido,res,copy_l);
		if (x==1)
			break;
		if (x==0) 
		{
			++f;
			liquido=copy_l-f;
			a=aa;
			b=bb;
			n=0;
		}
				
				
	}
	return 0;
	
}
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

Grazie, Gila, adesso il testimone è passato a me e ti farò avere i miei commenti appena possibile. Nome del file, per citarlo nei riferimenti, bottiglie.c.
Ciao
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Se non ti dovesse dire nulla l'array che ho nel programma, e come viene riempito, sappi che ho usato questo metodo:
https://www.youtube.com/watch?v=gfC0zVLOBAc

Poi per 3 o più incognite, un po' di spunti li ho letti, è che davvero non ho tempo, e la sera dopo il lavoro sono cotto.
Avatar utente
BlueEyes
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1330
Iscrizione: giovedì 15 marzo 2012, 14:08

Re: aiuto matematico

Messaggio da BlueEyes »

Ho cominciato a capire, Gila. Ecco i miei 3 test, che ho effettuato poco fa. Ci siamo, il procedimento mi piace. Con le diofantee a 2 variabili non abbiamo alcun problema. Ciao, buon long WE
Spoiler
Mostra

Codice: Seleziona tutto

Test#1 (ammette soluzioni) OK, lo scarto è nullo
Equazione diofantea data: a=7 b=3 liquido=53
x=2 y=13
LIQUIDO IMBOTTIGLIATO: cl 53
scarto: 0

------------
Test #2 (ammette soluzioni) OK, lo scarto è nullo
Equazione diofantea data: a=8 b=5 liquido=81
x=2 y=13
LIQUIDO IMBOTTIGLIATO: cl 81
scarto: 0

------------
Test#3 (NON ammette soluzioni) e difatti lo scarto NON è nullo, OK
--------------------------------------------------------------------
Qui si potrebbe ovviare con un IF-THEN iniziale
  Se (a+b) > liquido
  break [=non iniziare a calcolare nulla]

cl 26: impossibile frazionario
cl 25: impossibile frazionario
cl 24: impossibile frazionario
cl 23: impossibile frazionario
cl 22: impossibile frazionario
cl 21: impossibile frazionario
cl 20: impossibile frazionario
cl 19: impossibile frazionario
cl 18: impossibile frazionario
cl 17: impossibile frazionario
cl 16: impossibile frazionario
cl 15: impossibile frazionario
cl 14: impossibile frazionario
cl 13: impossibile frazionario
cl 12: impossibile frazionario
cl 11: impossibile frazionario
cl 10: impossibile frazionario
cl 9: impossibile frazionario
cl 8: impossibile frazionario
cl 7: impossibile frazionario
cl 6: impossibile frazionario
cl 5: impossibile frazionario
cl 4: impossibile frazionario
cl 3: impossibile frazionario
cl 2: impossibile frazionario
cl 1: impossibile frazionario
Equazione diofantea data: a=4 b=1 liquido=0
x=0 y=0
LIQUIDO IMBOTTIGLIATO: cl 0
scarto: 26
Edit. Un breve inciso, per ricordare la condizione che lega i tre termini del problema, mostrata nello screenshot derivato dal video del post precedente.
Edit2. C'è un problema, Gila, mancano per es. le due soluzioni (30,15) e (60,10) dell'esempio seguente. Mi fermo qui, per adesso (02/giu, mattino). Aggiungo che la soluzione (0,120), così come la (120,0), non dovrebbe essere mostrata. C'è qualcosa da aggiustare nel codice di bottiglie.c. L'equazione ammette 18 soluzioni intere, come in figura. Ciao

Codice: Seleziona tutto

Equazione diofantea data: a=1 b=6 liquido=120
x=0 y=120
LIQUIDO IMBOTTIGLIATO: cl 120
scarto: 0
Allegati
diof2-esempio.PNG
bezout.png
Ultima modifica di BlueEyes il venerdì 2 giugno 2017, 10:23, modificato 1 volta in totale.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: aiuto matematico

Messaggio da gila75 »

Appena posso guardo
EDIT:
La "mia soluzione", trova la prima coppia valida positiva con x al valore minore e si ferma.
Non ero interessato per il problema "bottiglie" alle varie soluzioni possibili, ma si potrebbe integrare.
il fatto di non mettere l'if iniziale: cioè non partire nemmeno se il liquido è minore della somma delle bottiglie,
è perchè inizialmente volevo fare test sui risultati negativi.
Edit_2

Si può fare anche così se si vuole una lista completa delle soluzioni:
a=1, b=2 liquido=120

Codice: Seleziona tutto

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



int mcd(int min,int max, int tab[][4],int *n);
void min_max (int *a,int *b);
void stampa (int n,int tab[][4]);
int bez (int n,int tab[][4],int liquido);
int bez_2 (int n,int tab[][4],int liquido);
void init_array(int tab[][4],int a,int b);
void riduci(int *a,int *b, int *liquido,int mcd);
int test(int mcd, int *l, int *f, int copy_l,int *n);
int risolvi (int p,int a, int b,int liquido,int mcd,int copy_l);


//***********************************************
// scambia numeri per trovare il massimo dei 2
//***********************************************
void min_max (int *a,int *b)
{
	int temp;
	if (*a<*b)
	{
		temp=*a;
		*a=*b;
		*b=temp;
	}
}

//***********************************************
// trova MCD metodo di Eulero
//***********************************************
int mcd(int min, int max,int tab[][4],int *n)
{
	int r = 1;
	int res;
	
	if (min == 0)
    	return max;
    else
    	while (r > 0)
		{
       		r = max % min;
			res=max/min;
        	max = min;
        	min = r;
			tab[*n+1][0]=min;
			tab[*n][1]=res;
			*n=(*n)+1;
		}
	
	return max;
}

//***********************************************
// test: se il liquido non è un multiplo dei
// 2 membri (75,33 nel mio) caso
// il risultato sarà frazionario e a me non va bene
//*************************************************
int test(int mcd, int *l, int *f, int copy_l,int *n)
{
	if  ( (*l%mcd)!=0)
	{	
		printf("cl %d: impossibile frazionario\n",*l);
		*f=*f+1;
		*l=copy_l-*f;
		*n=0;
		return 0;
	}
		
	return 1;
	
}

void riduci(int *a,int *b, int *liquido,int mcd)
{
	
	if ( (*liquido%mcd)==0 )
	{
		*a=*a/mcd;
		*b=*b/mcd;
		*liquido=*liquido/mcd;
		
		
	}
}

//***********************************************
// preparo l'array per il calcolo
// dei coefficienti di Bezout
//***********************************************
void init_array(int tab[][4],int a,int b)
{
	int r,c;
	for (r=0; r<50; r++)
	{
		for (c=0; c<4; c++)
			tab[r][c]=0;
	}
		
	tab[0][0]=a;
	tab[1][0]=b;
	tab[0][2]=1;
	tab[1][3]=1;
}
//***********************************************
// calcolo identità p di Bezout
//***********************************************
int bez (int n,int tab[][4], int liquido)
{
	int i;
	for (i=0; i<n; i++)
	{
		tab[i+2][2]=tab[i][2]-(tab[i+1][1]*tab[i+1][2]);
	}
	
	return tab[n-1][2]*liquido;
}


int bez_2(int n,int tab[][4],int liquido)
{
	int i;
	for (i=0; i<n; i++)
	{
		tab[i+2][3]=tab[i][3]-(tab[i+1][1]*tab[i+1][3]);
	}
	return tab[n-1][3]*liquido;
}

//***********************************************
// eventuale stampa per vedere la matrice
// che mi permette di vedere i passaggi
// e le identità di B.
//***********************************************
void stampa (int n,int tab[][4])
{
	int r,c;
	for (r=0; r<n; r++)
	{
		for (c=0; c<4; c++)
		{
			printf ("%d ", tab[r][c]);
		}
		puts("");
	}
	puts("-------------------");
}

//***********************************************
// calcola prima x, poi y
//***********************************************
	
int risolvi (int p,int a,int b,int liquido,int mcd,int copy_l)
{
	int res,x,y;
	int cont=0;
	printf ("__a=%d\n",a);
	res=p/b;	
	x=p-(res*b);
	y=(liquido-(a*x))/b;
	//printf ("Negativi: x=%d y=%d\n",x,y);
	if (x>=0 && y>=0)
	{
		printf ("x(6cl)=%d y(1cl)=%d\n",x,y);
		puts ("SOLUZIONE BASE");
		printf ("LIQUIDO IMBOTTIGLIATO: cl %d\n", (a*x+b*y)*mcd);
		printf ("scarto: %d\n", (copy_l-(a*x*mcd+b*y*mcd)));
		cont++;
		while (x>=0 && y>=0)
		{
			x=x+b;
			y=(liquido-(a*x))/b;
			if (x>=0 && y>=0)
			{
				printf ("x(6cl)=%d y(1cl)=%d\n",x,y);
				cont++;
			}
		} 
		printf ("soluzioni positive intere=%d\n", cont);
		return 1;
	}
	return 0;
	
}

	


int main (void)
{
	int a=1; //x
	int b=6; //y
	int liquido=120;
	int copy_l=liquido;
    int aa=a;
	int bb=b;
	int res,p,x,t,q  ;
	int tab[50][4];
	int n;
	int f=0;
	
	while (1)  
	{
		while(1)
		{
			min_max(&a,&b); 
			init_array(tab,a,b);
			res=mcd(a,b,tab,&n);
			t=test(res,&liquido,&f,copy_l,&n);
			if (t==1)
				break;
		}
			
		riduci (&a,&b,&liquido,res);
		p=bez(n,tab,liquido);
		q=bez_2(n,tab,liquido);
		//stampa(n,tab);
		
			
		x=risolvi(p,a,b,liquido,res,copy_l);
		if (x==1)
			break;
		if (x==0) 
		{
			++f;
			liquido=copy_l-f;
			a=aa;
			b=bb;
			n=0;
		}
				
				
	}
	return 0;
	
}
output:

Codice: Seleziona tutto

gila@gila-pc:~/Scrivania$ ./xx
x(6cl)=0 y(1cl)=120
SOLUZIONE BASE
LIQUIDO IMBOTTIGLIATO: cl 120
scarto: 0
x(6cl)=1 y(1cl)=114
x(6cl)=2 y(1cl)=108
x(6cl)=3 y(1cl)=102
x(6cl)=4 y(1cl)=96
x(6cl)=5 y(1cl)=90
x(6cl)=6 y(1cl)=84
x(6cl)=7 y(1cl)=78
x(6cl)=8 y(1cl)=72
x(6cl)=9 y(1cl)=66
x(6cl)=10 y(1cl)=60
x(6cl)=11 y(1cl)=54
x(6cl)=12 y(1cl)=48
x(6cl)=13 y(1cl)=42
x(6cl)=14 y(1cl)=36
x(6cl)=15 y(1cl)=30
x(6cl)=16 y(1cl)=24
x(6cl)=17 y(1cl)=18
x(6cl)=18 y(1cl)=12
x(6cl)=19 y(1cl)=6
x(6cl)=20 y(1cl)=0
soluzioni positive intere=21
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 9 ospiti