Ocena użytkownikóww: ***** / 5
Nadesłany przez Tomasz Lubiński, 31 lipca 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
Euler.java:
import java.util.Random;
//Tomasz Lubiński (c)2007
//www.algorytm.org
//Generowanie gafu z cyklem Eulera
public class Euler {
public static short[][] genGraphWithEuler(int n, int b) {
short result[][] = new short[n][n];
Random rand = new Random();
//clear graph
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
result[i][j] = 0;
//generate graph with given n and b
for (int i=1; i<n; i++)
for (int j=0; j<i; j++)
if (rand.nextInt(100)<b) {
result[i][j] = 1;
result[j][i] = 1;
}
//modify to have EULER
for (int i=0; i<n-1; i++) {
//calculate degree
int deg = 0;
for (int j=0; j<n; j++)
if (result[i][j]>0)
deg++;
//check if degree is even
if (deg%2 != 0) {
int x = rand.nextInt(n-i-1)+i+1;
if (result[i][x]>0) {
result[i][x] = 0;
result[x][i] = 0;
} else {
result[i][x] = 1;
result[x][i] = 1;
}
}
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
int n;
int b;
short graph[][];
System.out.println("Podaj liczbe wierzcholkow grafu");
n = Console.readInt("");
System.out.println("Podaj stopień nasycenia grafu (w %)");
b = Console.readInt("");
graph = genGraphWithEuler(n, b);
for (int i=0; i<n; i++){
System.out.println();
for (int j=0; j<n; j++) {
System.out.print(graph[i][j] + " ");
}
}
System.out.println();
}
}