👤

Să se implementeze algoritmul din imagine (în Java).

Vă rog!​


Să Se Implementeze Algoritmul Din Imagine În Java Vă Rog class=

Răspuns :

1. Dupa rularea mai multor exemple, se observa ca solutia a 2-a este un pic mai eficienta decat prima.

2. Vad doar 20, dar p se poate intrerupe pentru executia lui q dupa ce temp a luat valoarea lui n si inainte ca n sa fie actualizat, si atunci n va avea la valoarea 10, astfel n la final poate avea valori de la 10 la 20

3. Pana acum am vazut doar 20

Pentru 1 si 3 am atasat implementarile mele ale algoritmilor:

import java.util.Arrays;

import java.util.Iterator;

import java.util.Scanner;

import static java.lang.Integer.min;

public class Partea_1 {

   private static int Thread_exec_left = 0;

   private static final int N_MAX = 100000000;

   private static boolean[] prim = new boolean[N_MAX];

   public static void main(String[] args) {

       Scanner sc = new Scanner(System.in);

       int n = sc.nextInt();

       int k = sc.nextInt();

       int q = n / k, r = n % k;

       Thread_exec_left = k;

       long t1 = System.nanoTime();

       for(int i = 0; i < k; i++){

           new Thread(new S1(k, q, new I(i+1, n, q))).start();

       }

       while(Thread_exec_left != 0) // asteapta toate thread-urile sa termine executia

           Thread.yield();

       long t2 = System.nanoTime();

       System.out.println("Solutia 1: " + (t2 - t1) + " nanosecunde");

       Arrays.fill(prim, false);

       Thread_exec_left = k;

       t1 = System.nanoTime();

       for(int i = 0; i < k; i++){

           new Thread(new S2(new M(n, k, i+1))).start();

       }

       while(Thread_exec_left != 0) // asteapta toate thread-urile sa termine executia

           Thread.yield();

       t2 = System.nanoTime();

       System.out.println("Solutia 2: " + (t2 - t1) + " nanosecunde");

   }

   private static boolean prim_func(int x){ // functie care verifica daca un numar e prim

       if(x < 2)return false;

       if(x < 4)return true;

       int v = x % 6;

       if(v != 1 && v != 5)

           return false;

       for(v = 3; v * v <= x; v += 2)

           if(x % v == 0)

               return false;

       return true;

   }

   static class S1 implements Runnable { // Pentru solutia 1

       int k,q;

       I interval;

       S1(int k, int q, I interval){

           this.k = k;

           this.q = q;

           this.interval = interval;

       }

       @Override

       public void run() {

           for(int x : interval){

               if(prim_func(x)){

                   synchronized (this){

                       prim[x] = true;

                   }

               }

           }

           synchronized (this){

               int temp = Thread_exec_left;

               Thread_exec_left = temp - 1;

           }

       }

   }

   static class S2 implements Runnable { // Pentru solutia 2

       M multime;

       S2(M multime){

           this.multime = multime;

       }

       @Override

       public void run() {

           for(int x : multime){

               if(prim_func(x)){

                   synchronized (this){

                       prim[x] = true;

                   }

               }

           }

           synchronized (this){

               int temp = Thread_exec_left;

               Thread_exec_left = temp - 1;

           }

       }

   }

   static class I implements Iterable<Integer>{

       int lower, higher;

       int ptr = 0;

       I(int indice, int n, int q){

           lower = (indice - 1) * q + indice;

           higher = min(indice * (q + 1), n);

           ptr = lower;

       }

       @Override

       public Iterator<Integer> iterator() {

           return new Iterator<Integer>() {

               @Override

               public boolean hasNext() {

                   return ptr <= higher;

               }

               @Override

               public Integer next() {

                   return ptr++;

               }

           };

       }

   }

   static class M implements Iterable<Integer> {

       int k, j;

       int ptr = 0;

       int n;

       M(int n, int k, int j){

           this.n = n;

           this.k = k;

           this.j = j;

       }

       int gen(){

           if(j == 1 && ptr == 0)

               return k + 1;// returnam k+1 in loc de 1, care oricum nu e prim

           return ptr * (k + 1) + j;

       }

       @Override

       public Iterator<Integer> iterator() {

           return new Iterator<Integer>() {

               @Override

               public boolean hasNext() {

                   return gen() <= n;

               }

               @Override

               public Integer next() {

                   int val = gen();

                   ptr++;

                   return val;

               }

           };

       }

   }

}

//Pentru partea cu numarare concurenta

public class NumarareConcurenta implements Runnable {

   static int n = 0;

   public static void main(String[] args) {

       n = 0;

       Thread t1 = new Thread(new NumarareConcurenta());

       Thread t2 = new Thread(new NumarareConcurenta());

       t1.start();

       t2.start();

       try {

           t1.join();

           t2.join();

       } catch (InterruptedException e) {

           e.printStackTrace();

       }

       System.out.println(n);

   }

   @Override

   public void run() {

       int temp;

       for (int i = 0; i < 10; i++) {

           temp = n;

           n = temp + 1;

       }

   }

}