Pages: [1] 2 3   Go Down
Print
Author Topic: Soluzione Gara di Programmazione 2 - COMPETIZIONE N3  (Read 5021 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« on: 17-04-2011, 23:17:06 »

Questa è la mia soluzione voi come l'avete fatto?  pc
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #1 on: 17-04-2011, 23:30:28 »

Io ho fatto così:
Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class SS7_003411
{
public static int key,righe=0;
public  static void LeggiFile(String nome) throws IOException
{
BufferedReader in = null;
BufferedWriter out= null;
try
{
in=new BufferedReader(new FileReader("input.txt"));
out=new BufferedWriter(new FileWriter("SS7_003411.txt"));
String str="";
key=converti(in.readLine());
while((str=in.readLine())!=null)//Fino a quando non arrivo a fine file
{
righe++;
if(analizza(str))
{
out.write(toRoman(righe));
out.newLine();
}
}
}
finally
{
in.close();
out.close();
}

}
public static boolean analizza(String s)
{

StringBuffer str=new StringBuffer();
int control=0,j=0;

for(int i=0;i<s.length();i++)
{
if(s.charAt(i)==',')
control++;
}
int []numeri=new int[control+1] ;
control=0;
for(int i=0;i<s.length();i++)
{
if((s.charAt(i)>64 && s.charAt(i)<91 && s.charAt(i)!=',') || (s.charAt(i)>97 && s.charAt(i)<122))
control++;

if(control>=2 && s.charAt(i)!=',')
{
str.append(s.charAt(i));

}
if(s.charAt(i)==',' || i==s.length()-1 )
{

numeri[j]=converti(str.toString());

j++;
if(str!=null)
str=new StringBuffer();
control=0;
}
}
int []a=mergeSort(numeri);
int min=0,max=0;

for(int i=0; i<a.length;i++)
{
max+=a[i]*(i+1);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
min+=a[i]*(a.length-i);//a[0]*a.length+a[1]*(a.length-1)+...+a[a.length-1]*1
}
if(key==max || key == min)//Mi conviene permutare perchè la stringa POTREBBE ESSERE quella corretta
return true;

if(key<max && key>min)  //Mi conviene permutare perchè la stringa POTREBBE ESSERE quella corretta
{
if(permuta(a,0,a.length-1))
return true;
}

return false;
}

//Le permutazioni vengono fatte usando la disuguaglianza del riarrangiamento così da evitare permutazioni su stringhe inutili


static boolean permuta(int[] lista, int da, int a) {

int scambio;
int k;
int min=0;
if ( (a - da) >= 1 ) {
    for ( k = a; k >= da; k-- ) {
scambio = lista[k];
lista[k] = lista[a];
lista[a] = scambio;
for(int i=0; i<lista.length;i++)
{
min+=lista[i]*(lista.length-i);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
}
if(min==key)
return true;
else
min=0;
permuta( lista, da, a-1 );


for(int i=0; i<lista.length;i++)
{
min+=lista[i]*(lista.length-i);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
}
if(min==key)
return true;
else
min=0;
scambio = lista[k];
lista[k] = lista[a];
lista[a] = scambio;
for(int i=0; i<lista.length;i++)
{
min+=lista[i]*(lista.length-i);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
}

if(min==key)
return true;
else
min=0;
    }
}
return false;
}
//Convertitore da numeri romani a numeri decimali
public static int converti(String s) {

int [] arrayInteri=new int [s.length()];


for(int i= 0; i <arrayInteri.length; i++){
switch(s.charAt(i)){
case 'I':{arrayInteri[i]=1;break;}
case 'V' :{arrayInteri[i]=5;break;}
case 'X':{arrayInteri[i]=10;break;}
case 'L':{arrayInteri[i]=50;break;}
case 'C':{arrayInteri[i]=100;break;}
case 'D':{arrayInteri[i]=500;break;}
case 'M':{arrayInteri[i]=1000;break;}
}
}

int numeroConvertito=arrayInteri[arrayInteri.length-1];
for(int i=0;i<arrayInteri.length-1;i++)
{
numeroConvertito = arrayInteri[i]>=arrayInteri[i+1] ? numeroConvertito+arrayInteri[i] : numeroConvertito-arrayInteri[i];
}
return numeroConvertito;
}

//Realizziamo ora un convertitore da Decimali a Romani
public static String toRoman(int decimal )
{
StringBuffer s=new StringBuffer("");
String [] romani={"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int [] decimali={1000, 900, 500, 400,  100,   90,  50, 40,   10,    9,   5,   4,    1};
for(int i=0;i<romani.length;i++)
{
while(decimal >= decimali[i])
{
decimal-=decimali[i];
s.append(romani[i]);
}

}

return s.toString();
}
//Ordiniamo i numeri convertiti da romani in decimali usando l'algoritmo MergeSort
private static void mergeSort(int[] a, int[] vectorTemp, int left, int right) {
if (left < right) {
int center = (left + right) /2;
mergeSort (a, vectorTemp, left, center);
mergeSort (a, vectorTemp, center+1, right);
merge (a, vectorTemp, left, center+1, right);
}
}

public static int[] mergeSort(int[] a) {
int vectorTemp [];
vectorTemp = new int [a.length];
mergeSort (a, vectorTemp, 0, a.length-1);
return a;
}

private static void merge(int[] a, int[] vectorAux, int posLeft, int posRight, int posEnd) {
int endLeft = posRight -1;
int posAux = posLeft;
int numElemen = posEnd - posLeft +1;

while (posLeft <= endLeft && posRight <=posEnd) {
if ((a[ posLeft ])< (a[posRight]))
vectorAux [posAux++]=a[posLeft++];
else
vectorAux [posAux++] = a[posRight++];
}

while (posLeft <= endLeft)
vectorAux [posAux++]=a[posLeft++];

while (posRight <= posEnd)
vectorAux [posAux++]=a[posRight++];

for (int i=0;i<numElemen;i++,posEnd--)
a[posEnd]=vectorAux[posEnd];
}

public static void main(String args[])throws IOException
{
// long start=System.nanoTime();
LeggiFile("input.txt");
// long finish=System.nanoTime()-start;
// System.out.print(finish/Math.pow(10, 9));
}
}
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #2 on: 18-04-2011, 00:27:31 »

Io ho fatto così:
Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class SS7_003411
{
public static int key,righe=0;
public  static void LeggiFile(String nome) throws IOException
{
BufferedReader in = null;
BufferedWriter out= null;
try
{
in=new BufferedReader(new FileReader("input.txt"));
out=new BufferedWriter(new FileWriter("SS7_003411.txt"));
String str="";
key=converti(in.readLine());
while((str=in.readLine())!=null)//Fino a quando non arrivo a fine file
{
righe++;
if(analizza(str))
{
out.write(toRoman(righe));
out.newLine();
}
}
}
finally
{
in.close();
out.close();
}

}
public static boolean analizza(String s)
{

StringBuffer str=new StringBuffer();
int control=0,j=0;

for(int i=0;i<s.length();i++)
{
if(s.charAt(i)==',')
control++;
}
int []numeri=new int[control+1] ;
control=0;
for(int i=0;i<s.length();i++)
{
if((s.charAt(i)>64 && s.charAt(i)<91 && s.charAt(i)!=',') || (s.charAt(i)>97 && s.charAt(i)<122))
control++;

if(control>=2 && s.charAt(i)!=',')
{
str.append(s.charAt(i));

}
if(s.charAt(i)==',' || i==s.length()-1 )
{

numeri[j]=converti(str.toString());

j++;
if(str!=null)
str=new StringBuffer();
control=0;
}
}
int []a=mergeSort(numeri);
int min=0,max=0;

for(int i=0; i<a.length;i++)
{
max+=a[i]*(i+1);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
min+=a[i]*(a.length-i);//a[0]*a.length+a[1]*(a.length-1)+...+a[a.length-1]*1
}
if(key==max || key == min)//Mi conviene permutare perchè la stringa POTREBBE ESSERE quella corretta
return true;

if(key<max && key>min)  //Mi conviene permutare perchè la stringa POTREBBE ESSERE quella corretta
{
if(permuta(a,0,a.length-1))
return true;
}

return false;
}

//Le permutazioni vengono fatte usando la disuguaglianza del riarrangiamento così da evitare permutazioni su stringhe inutili


static boolean permuta(int[] lista, int da, int a) {

int scambio;
int k;
int min=0;
if ( (a - da) >= 1 ) {
    for ( k = a; k >= da; k-- ) {
scambio = lista[k];
lista[k] = lista[a];
lista[a] = scambio;
for(int i=0; i<lista.length;i++)
{
min+=lista[i]*(lista.length-i);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
}
if(min==key)
return true;
else
min=0;
permuta( lista, da, a-1 );


for(int i=0; i<lista.length;i++)
{
min+=lista[i]*(lista.length-i);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
}
if(min==key)
return true;
else
min=0;
scambio = lista[k];
lista[k] = lista[a];
lista[a] = scambio;
for(int i=0; i<lista.length;i++)
{
min+=lista[i]*(lista.length-i);//a[0]*1+a[1]*2+...+a[a.length-1]*a.length
}

if(min==key)
return true;
else
min=0;
    }
}
return false;
}
//Convertitore da numeri romani a numeri decimali
public static int converti(String s) {

int [] arrayInteri=new int [s.length()];


for(int i= 0; i <arrayInteri.length; i++){
switch(s.charAt(i)){
case 'I':{arrayInteri[i]=1;break;}
case 'V' :{arrayInteri[i]=5;break;}
case 'X':{arrayInteri[i]=10;break;}
case 'L':{arrayInteri[i]=50;break;}
case 'C':{arrayInteri[i]=100;break;}
case 'D':{arrayInteri[i]=500;break;}
case 'M':{arrayInteri[i]=1000;break;}
}
}

int numeroConvertito=arrayInteri[arrayInteri.length-1];
for(int i=0;i<arrayInteri.length-1;i++)
{
numeroConvertito = arrayInteri[i]>=arrayInteri[i+1] ? numeroConvertito+arrayInteri[i] : numeroConvertito-arrayInteri[i];
}
return numeroConvertito;
}

//Realizziamo ora un convertitore da Decimali a Romani
public static String toRoman(int decimal )
{
StringBuffer s=new StringBuffer("");
String [] romani={"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int [] decimali={1000, 900, 500, 400,  100,   90,  50, 40,   10,    9,   5,   4,    1};
for(int i=0;i<romani.length;i++)
{
while(decimal >= decimali[i])
{
decimal-=decimali[i];
s.append(romani[i]);
}

}

return s.toString();
}
//Ordiniamo i numeri convertiti da romani in decimali usando l'algoritmo MergeSort
private static void mergeSort(int[] a, int[] vectorTemp, int left, int right) {
if (left < right) {
int center = (left + right) /2;
mergeSort (a, vectorTemp, left, center);
mergeSort (a, vectorTemp, center+1, right);
merge (a, vectorTemp, left, center+1, right);
}
}

public static int[] mergeSort(int[] a) {
int vectorTemp [];
vectorTemp = new int [a.length];
mergeSort (a, vectorTemp, 0, a.length-1);
return a;
}

private static void merge(int[] a, int[] vectorAux, int posLeft, int posRight, int posEnd) {
int endLeft = posRight -1;
int posAux = posLeft;
int numElemen = posEnd - posLeft +1;

while (posLeft <= endLeft && posRight <=posEnd) {
if ((a[ posLeft ])< (a[posRight]))
vectorAux [posAux++]=a[posLeft++];
else
vectorAux [posAux++] = a[posRight++];
}

while (posLeft <= endLeft)
vectorAux [posAux++]=a[posLeft++];

while (posRight <= posEnd)
vectorAux [posAux++]=a[posRight++];

for (int i=0;i<numElemen;i++,posEnd--)
a[posEnd]=vectorAux[posEnd];
}

public static void main(String args[])throws IOException
{
// long start=System.nanoTime();
LeggiFile("input.txt");
// long finish=System.nanoTime()-start;
// System.out.print(finish/Math.pow(10, 9));
}
}
Buono, abbastanza veloce!  ok
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #3 on: 18-04-2011, 09:49:04 »

Ecco il mio...è un pò lungo a causa dei 2 metodi per i num romani  yoh e i due per l'ordinamento crescente e decrescente  yoh

Code:
import java.io.*;

class myScanner {
private BufferedReader input = null;
private int puntatore = 0,length = 0;
private char[] linea;

myScanner( BufferedReader in ) {
input = in;
}

public void readLine() throws IOException {
linea = new char[5000];
puntatore = length = 0;
do {
linea[length++] = (char)input.read();
} while( linea[length-1] != '\n' );
}

public void next() {
do {
puntatore++;
} while( linea[puntatore] != ' ' );
puntatore++;
}

public char[] nextRoman() {
int i = puntatore;
do {
i++;
} while( linea[i] != ',' && linea[i] != '\n' );
char[] ret = new char[i-puntatore];
for(int j=0; j<ret.length; j++)
ret[j] = linea[puntatore++];
puntatore += 2;
return ret;
}

public boolean hasNext() {
return ( length > puntatore );
}
}

public class M01_000001
{
static BufferedReader input = null;
static BufferedWriter output = null;
static myScanner scanner = null;

static final int[] RomanValue = new int[89];
static final int[] RomanTable = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
static final String[] RomanTableChar = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
static int linea = 1, K;

public static void parseFile(String inputFile,String outputFile) throws Exception
{
try {
input = new BufferedReader(new FileReader(new File(inputFile)));
output = new BufferedWriter(new FileWriter(new File(outputFile)));

RomanValue[73] = 1;
RomanValue[86] = 5;
RomanValue[88] = 10;
RomanValue[76] = 50;
RomanValue[67] = 100;
RomanValue[68] = 500;
RomanValue[71] = 1000;

scanner = new myScanner(input);
K = roman2int(input.readLine());

while(input.ready())
{
scanner.readLine();
int n = 0;
int[] buf = new int[30];

while( scanner.hasNext() ) {
scanner.next();
char[] c = scanner.nextRoman();
int num = roman2int(c);
buf[n++] = num;
}

int max = 0,min = 0;
sort( buf,n );
for(int i = 0,m = 1; i<n; i++,m++)
max += m*buf[i];
sort2( buf,n );
for(int i = 0,m = 1; i<n; i++,m++)
min += m*buf[i];

boolean trovato = false;
if( (K > min && K < max) || (K == max || K == min) )
trovato = Fuchs_perm(buf,n);

if(trovato) {
num2roman(linea);
output.write("\n");
}

linea++;
}
}
finally {
if (output != null) output.close();
if (input != null) input.close();
}
}

public static int roman2int( char[] num )
{
char k,m = 0;
int ret = 0;
for( int i=0; i<num.length; i++ ) {
k = num[i];
m = 0;
if( i+1<num.length )
m = num[i+1];
if( ((int)k == 73 || (int)k == 88 || (int)k == 67) && RomanValue[(int)k] < RomanValue[(int)m] ) {
ret += RomanValue[(int)m]-RomanValue[(int)k];
i++;
}
else ret += RomanValue[(int)k];
}
return ret;
}

public static int roman2int( String num )
{
char k,m = 0;
int ret = 0;
for( int i=0; i<num.length(); i++ ) {
k = num.charAt(i);
m = 0;
if( i+1<num.length() )
m = num.charAt(i+1);
if( ((int)k == 73 || (int)k == 88 || (int)k == 67) && RomanValue[(int)k] < RomanValue[(int)m] ) {
ret += RomanValue[(int)m]-RomanValue[(int)k];
i++;
}
else ret += RomanValue[(int)k];
}
return ret;
}

public static boolean Fuchs_perm( int[] buf,int string_length ) throws IOException
{
int ris = 0;
for( int k = 0,m = 1; k<string_length; k++,m++ )
ris += m*buf[k];

if (ris == K)
return true;
int[] p = new int[string_length];
int i = 1;
while(i < string_length) {
if ( p[i] < i ) {
int j = i % 2 * p[i];
int tmp = buf[j];
buf[j] = buf[i];
buf[i] = tmp;

ris = 0;
for( int k = 0,m = 1; k<string_length; k++,m++ )
ris += m*buf[k];

if (ris == K)
return true;

p[i]++;
i = 1;
} else {
p[i] = 0;
i++;
}
}
return false;
}

public static void num2roman(int number) throws IOException
{
for (int i = 0; i < 13; i++) {
while ( number >= RomanTable[i] ) {
output.write(RomanTableChar[i]);
number -= RomanTable[i];
}
}
}

public static void sort( int a[],int length ) throws Exception {
for (int i=1; i<length; i++) {
int j = i;
int B = a[i];
while ((j > 0) && (a[j-1] > B)) {
a[j] = a[j-1];
j--;
}
a[j] = B;
}
}

public static void sort2( int a[],int length ) throws Exception {
for (int i=1; i<length; i++) {
int j = i;
int B = a[i];
while ((j > 0) && (a[j-1] < B)) {
a[j] = a[j-1];
j--;
}
a[j] = B;
}
}

public static void main( String[] args ) throws Exception {
parseFile("input.txt","M01_000001.txt");
}
}
Logged

Ciò che è nostro è stato in campo sudato....ciò che vostro è stato in aula assegnato.
In serie B non sei mai stato perchè la prescrizione t'ha salvato.
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #4 on: 18-04-2011, 10:42:58 »

Potete aiutarmi a capire cosa rallenta il mio programma??  pray
Ho anche usato l'iterazione per le permutazioni anzichè la ricorsione 
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
fabryxio
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 343

Chi l'ha duro....... l'ha duro!


WWW
« Reply #5 on: 18-04-2011, 10:43:33 »

un pò + complicatello questo esercizio devo dire =S ma c sn riuscito!! nn è velocissimo ma ci sono riuscito!!
Logged

Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #6 on: 18-04-2011, 11:42:02 »

ma i vostri tempi? ... anche se non sono molto indicativi
Logged

Aliens Exist
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #7 on: 18-04-2011, 12:28:37 »

ma i vostri tempi? ... anche se non sono molto indicativi
Il mio 170.0ms usando System.currentTimeMillis()
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #8 on: 18-04-2011, 12:42:01 »

il mio 20 ms

@Zeloto
il tuo prog in realtà nn è lento, in realtà non esiste un metodo che riesce a calcolare le permutazioni velocemente, dato che ne deve sempre calcolare n!
La soluzione di questo programma era in realtà capire quando NON fare le permutazioni perchè si sà a priori che è inutile.

Io ad esempio prendevo i numeri delle righe e li ordinavo in senso crescente, svolgevo l'equazione e ricavavo il max...facevo lo stesso in senso decrescente ricavando il min...quindi tutti i valori possibili delle permutazioni ricadevano tra il max e min...se K era più piccolo o più grande era inutile calcolarsi tutto.
« Last Edit: 18-04-2011, 12:44:38 by R3m » Logged

Ciò che è nostro è stato in campo sudato....ciò che vostro è stato in aula assegnato.
In serie B non sei mai stato perchè la prescrizione t'ha salvato.
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #9 on: 18-04-2011, 13:30:46 »

il mio 20 ms

@Zeloto
il tuo prog in realtà nn è lento, in realtà non esiste un metodo che riesce a calcolare le permutazioni velocemente, dato che ne deve sempre calcolare n!
La soluzione di questo programma era in realtà capire quando NON fare le permutazioni perchè si sà a priori che è inutile.

Io ad esempio prendevo i numeri delle righe e li ordinavo in senso crescente, svolgevo l'equazione e ricavavo il max...facevo lo stesso in senso decrescente ricavando il min...quindi tutti i valori possibili delle permutazioni ricadevano tra il max e min...se K era più piccolo o più grande era inutile calcolarsi tutto.
Si lo so, infatti escludo anche le permutazioni superflue, non capisco in quale parte rallenta...perchè alla fine faccio il minimo indispensabile 
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #10 on: 18-04-2011, 13:36:54 »

Ho visto il programma sul tuo sito, ma non mi sembra che tu le escluda...c'è il metodo verificaPermutazione(numeri, numeri.length) che poi si calcola tutte le permutazioni...

Tra l'altro altro errore, o almeno, in questi esercizi è un errore, non usare le string cerca di usare i tipi primitivi...
Logged

Ciò che è nostro è stato in campo sudato....ciò che vostro è stato in aula assegnato.
In serie B non sei mai stato perchè la prescrizione t'ha salvato.
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #11 on: 18-04-2011, 13:55:19 »

Ho visto il programma sul tuo sito, ma non mi sembra che tu le escluda...c'è il metodo verificaPermutazione(numeri, numeri.length) che poi si calcola tutte le permutazioni...

Tra l'altro altro errore, o almeno, in questi esercizi è un errore, non usare le string cerca di usare i tipi primitivi...
Si ma il metodo verificaPermutazione(numeri, numeri.length) una volta trovata una permutazione (seguendo l'espressione x1 + 2x2 + 3x3 +...+ nxn) che sia uguale a K ritorna la riga e si ferma  
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #12 on: 18-04-2011, 14:14:33 »

ma quindi se i numeri ordinati in senso crescente erano maggiori di k si potevano scartare? 
Logged

Aliens Exist
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #13 on: 18-04-2011, 14:24:30 »

ma quindi se i numeri ordinati in senso crescente erano maggiori di k si potevano scartare? 
Che intendi? Considerando la riga x si potevano scartare le restanti permutazioni se già ne avevi trovata 1 tale che perm(x) = K
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #14 on: 18-04-2011, 14:26:09 »

Io ad esempio prendevo i numeri delle righe e li ordinavo in senso crescente, svolgevo l'equazione e ricavavo il max...facevo lo stesso in senso decrescente ricavando il min...quindi tutti i valori possibili delle permutazioni ricadevano tra il max e min...se K era più piccolo o più grande era inutile calcolarsi tutto.


intendo questo
Logged

Aliens Exist
Pages: [1] 2 3   Go Up
Print
Jump to: