.junk

Icon

Just another WordPress.com weblog

Cateva exercitii in Java

Backtracking – Problema celor n regine (in Java)

import java.io.*;
import java.util.*;

class Queens{
private static final String FileOutputName=”nRegine.out”;
public static void main(String[] args)
throws IOException{
PrintStream out=new PrintStream(new File(FileOutputName));
try{
System.out.print(“n=”);
Scanner sc=new Scanner(System.in);
if (!sc.hasNextInt()){
return;
}

int n=sc.nextInt();
int noSol=0;
int[] x=new int[n];
int k=0;
x[k]=-1;
while(k>=0){
boolean flag=false;
while(!flag && x[k]<n-1){
x[k]++;
flag=true;
for(int i=0;i<k;i++)
if ((x[i]==x[k]) || (Math.abs(x[i]-x[k])==k-i)) flag=false;
}
if (flag){
if (k==n-1){
for(int i:x){
out.print(i+1);
out.print(' ');
}
out.println();
noSol++;
}else
x[++k]=-1;
}else
k–;
}
out.println(n);
out.println(' ');
out.println(noSol);
}finally{
out.close();
}
}
}

Greedy – Problema programarii spectacolelor
import java.io.*;
import java.lang.*;
import java.util.*;

class Spectacol{
int hi, hf;
Spectacol(){}
Spectacol(int a,int b){
this.hi=a;
this.hf=b;
}

void afisare(){
System.out.println(“\nSpectacolul incepe la ” + hi + ” spectacolul se sfarseste la ” +hf);

}

}

class MainSpectacol{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
System.out.println(“Dati nr de spectacole:”);
int n=sc.nextInt();
Spectacol[] v = new Spectacol[n];
//v=new Spectacol[n];

for(int i=0;i<n;i++)
{
System.out.println("\nLa ce ora incepe spectacolul " +(i+1)+" ?");
int hinc=sc.nextInt();
System.out.println("\nLa ce ora se sfarseste spectacolul " +(i+1)+" ?");
int hsf=sc.nextInt();
//v[i]=new Spectacol(sc.nextInt(), sc.nextInt());
v[i]=new Spectacol(hinc, hsf);
}

System.out.println("\n");
for(int i=0;i<n;i++){v[i].afisare();}
System.out.println("\n");

for(int i=0;i<n-1;i++){
for(int j=i+1;jv[j].hf){
Spectacol aux=v[i];
v[i]=v[j];
v[j]=aux;
}
}
}

v[0].afisare();
int poz=0;

for(int i=1;iv[poz].hf){
v[i].afisare();
poz=i;
}
}
}
}

Recursivitate + Divide et Impera – Cel mai mare divizor comun al n numere

import java.io.*;
import java.util.*;

public class cmmdc{
private static final String FileInputName=”numere.in”;

private static int gcd(int a, int b){
while(b!=0){
int r=a%b;
a=b;
b=r;
}
return a;
}

private static int divide_et_impera(List a, int iMin, int iMax){
if (iMin<iMax){
int middle=(iMin+iMax)/2;
int d1=divide_et_impera(a, iMin, middle);
int d2=divide_et_impera(a,middle+1, iMax);
return gcd(d1,d2);
}
return 0 <= iMin&&iMin<a.size() ? a.get(iMin) : 0;

}

public static void main(String[] args) throws IOException{
List list=new ArrayList();
Scanner sc=new Scanner(new File(FileInputName));
try{
while(sc.hasNextInt()){
list.add(sc.nextInt());
}
int sz=list.size();
if (sz>0){
System.out.println(“cmmdc=” + divide_et_impera(list,0,sz-1));
}
}finally{
sc.close();
}
}
}

Sortare: QuickSort
import java.io.*;
import java.util.*;

public class qsort1{

private static final String FileInputName=”qsortin.txt”;
private static final String FileOutputName=”qsortout.txt”;

private static int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];

while (i <= j) {
while (arr[i] pivot)
j–;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j–;
}
};

return i;
}
private static void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index – 1)
quickSort(arr, left, index – 1);
if (index < right)
quickSort(arr, index, right);
}
public static void main(String[] args) throws IOException{
Scanner sc=null;
PrintStream out=null;

try{
out=new PrintStream(new File(FileOutputName));
sc=new Scanner(new File(FileInputName));

List list=new ArrayList();

while (sc.hasNextInt()){
list.add(sc.nextInt());
}

int idx=list.size();
int arr[]=new int[idx];

for(int i=0;i<idx;i++) arr[i]=list.get(i);

quickSort(arr, 0, idx-1);

for(int i=0;i=0 ) { // pentru fiu/frate inexistent, i=-1
x.fiu = new varf(i); creare(x.fiu);
}
System.out.print(“fratele lui ” + x.v + ” : “);
i = sc.nextInt();
if( i>=0 ) {
x.frate = new varf(i); creare(x.frate);
}
}

String pre(varf x) {
if (x==null) return “”;
else return x.v + ” ” + pre(x.fiu) + pre(x.frate);
}

void post(varf x) {
varf y = x.fiu;
while (y != null) { post(y); y = y.frate; }
System.out.print(x.v + ” “);
}
}

class Arbori {
public static void main(String[] s) {
varf Ob = new varf(); Ob.creare();
System.out.println( “Preordine:\t” + Ob.pre(varf.rad) );
System.out.print(“Postordine:\t”); Ob.post(varf.rad);
}
}

Arbori 2
import java.util.*;
class elem {
int i; elem st,dr; static elem rad;

elem() { }
elem(int ii) { i = ii; }

void creare() {
Scanner sc = new Scanner(System.in);
while ( sc.hasNextInt() ) rad = adaug(rad, sc.nextInt());
}

elem adaug(elem x, int i) {
if (x==null) x=new elem(i);
else if (i<x.i) x.st=adaug(x.st,i);
else x.dr=adaug(x.dr,i);
return x;
}

String parcurg(elem x) {
if (x==null) return("");
else return( parcurg(x.st) + x.i + " " + parcurg(x.dr));
}
}

class Arbsort {
public static void main(String arg[]) {
elem Ob = new elem();
Ob.creare();
System.out.println(Ob.parcurg(elem.rad));
}
}

Arbori 3
import java.util.Scanner;

Class Nod{

int inf;
Nod st, dr;
Nod(){}

Nod(int b){inf=b; st=null; dr=null;}
}

class Arbore{

Nod rad;

static Scanner sc=new Scanner(System.in);

void creare(){
rad=new Nod();
rad.inf=sc.nextInt);
creare_subarbore(rad);}

void creare_subarbore(Nod a){
//fiul stang

if (sc.hasNextInt()==true){
a.st=new Nod();
a.st.inf=sc.nextInt();

creare_subarbore(a.st);}

else {sc.next(); //sare caracterul care nu e int
a.st=null;}

//fiul drept…
}

void preordine(Nod a){
if (a!=null)
system.out.print(a.inf + " ");
preordine(a.st);
preordine(a.dr);
}

void inordine(Nod a){
if (a!=null)
inordine(a.st);
System.out.print(a.inf+" ");
inordine(a.dr);
}

}

Drum plan

import java.util.*;

class elem {
int i,j; elem prec;
static int m,n,i0,j0,ndepl=4;
static int[][] mat;
static int[][] depl = { {1,0,-1,0}, {0,-1,0,1} };

elem() {
int i,j;
Scanner sc = new Scanner(System.in);
System.out.print("m,n = "); m = sc.nextInt();
n = sc.nextInt(); // de fapt m+2,n+2
mat = new int[m][n];
for(i=1; i<m-1; i++)
for(j=1; j<n-1; j++) mat[i][j] = sc.nextInt();
for (i=0; i<n; i++) {mat[0][i] = 2; mat[m-1][i] = 2; }
for (j=0; j<m; j++) {mat[j][0] = 2; mat[j][n-1] = 2; }
System.out.print("i0,j0 = ");
i0 = sc.nextInt(); j0 = sc.nextInt();
}

elem(int ii, int jj, elem x) { i = ii; j = jj; prec = x; }

String print() {
if (prec == null) return "(" + i + "," + j + ")";
else return prec.print() + " " + "(" + i + "," + j + ")";
}

void back() { // backtracking pentru celula curenta
elem x; int ii,jj;
for (int k=0; k<ndepl; k++) {
ii = i+depl[0][k]; jj = j+depl[1][k];
if (mat[ii][jj] == 1);
else if (mat[ii][jj] == 2)
System.out.println(print());
else if (mat[ii][jj] == 0) {
mat[i][j] = -1;
x = new elem(ii,jj,this); x.back();
mat[i][j] = 0;
}
}
}
}

class DrumPlan {
public static void main(String[] args) {
new elem(); elem start = new elem(elem.i0,elem.j0,null);
start.back();
}
}

Filed under: Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: