Avatar billede Peter22 Nybegynder
14. november 2014 - 19:56 Der er 37 kommentarer

Algoritme

Hej :-)

er der nogle som vil hjælp mig med  opgaven.. opgaven går ud på at:

We are given an array that contains N numbers and would like to determine if there are two numbers
whose sum equals a given number K.
For example we may be given the sequence 4,1,5,2,6,3 and are asked to find a pair of numbers with a sum
of 10. In this example 4 and 6 is a valid result.

1) Implement an O(N2
) algorithm for solving the problem
2) Implement an O(N Log(N)) algorithm for solving the problem

jeg ved ikke hvordan jeg skal implementere det ....
Avatar billede arne_v Ekspert
14. november 2014 - 20:02 #1
re 1)

Maa kunne goeres med en dobbelt for loekke.
Avatar billede arne_v Ekspert
14. november 2014 - 20:05 #2
re 2)

Er mere tricky.

Men en sortering efterfulgt af en for loekke og en binaer soegning efter sum-current var maaske en loesning.
Avatar billede Peter22 Nybegynder
14. november 2014 - 20:19 #3
ok men jeg har noget kode hvis de gider at se om det er rigtigt til den første opgave ..

her er koden:

*/
public class QuickSort{

    public static void main(String args[]) {
   
        int[] input = {4 , 1, 5, 2, 6, 3};
        System.out.println("Before sorting : " + Arrays.toString(input));
        quickSort(input); // sort the integer array using quick sort algorithm
        System.out.println("After sorting : " + Arrays.toString(input));
   
     
    }

    /**
    * public method exposed to client, sorts given array using QuickSort
    * Algorithm in Java
    * @param array
    */
    public static void quickSort(int[] array) {
        recursiveQuickSort(array, 0, array.length - 1);
    }

    /**
    * Recursive quicksort logic
    *
    * @param array input array
    * @param startIdx start index of the array
    * @param endIdx end index of the array
    */
    public static void recursiveQuickSort(int[] array, int startIdx, int endIdx) {
   
        int idx = partition(array, startIdx, endIdx);

        // Recursively call quicksort with left part of the partitioned array
        if (startIdx < idx - 1) {
            recursiveQuickSort(array, startIdx, idx - 1);
        }

        // Recursively call quick sort with right part of the partitioned array
        if (endIdx > idx) {
            recursiveQuickSort(array, idx, endIdx);
        }
    }

    /**
    * Divides array from pivot, left side contains elements less than
    * Pivot while right side contains elements greater than pivot.
    *
    * @param array array to partitioned
    * @param left lower bound of the array
    * @param right upper bound of the array
    * @return the partition index
    */
    public static int partition(int[] array, int left, int right) {
        int pivot = array[left]; // taking first element as pivot

        while (left <= right) {
            //searching number which is greater than pivot, bottom up
            while (array[left] < pivot) {
                left++;
            }
            //searching number which is less than pivot, top down
            while (array[right] > pivot) {
                right--;
            }

            // swap the values
            if (left <= right) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;

                //increment left index and decrement right index
                left++;
                right--;
            }
        }
        return left;
    }
}
Avatar billede arne_v Ekspert
14. november 2014 - 20:24 #4
Nu er jeg lidt forvirret.

Er opgaven at finde tal med en given sum eller at lave quicksort?
Avatar billede arne_v Ekspert
14. november 2014 - 20:24 #5
PS: Jeg vil ioevrigt anbefale at tage det midterste som pivot fremfor det foerste!
Avatar billede Peter22 Nybegynder
14. november 2014 - 20:33 #6
opgaven er at finde tal med given sum.. jeg ved ikke helt hvordan jeg skal implementere det
Avatar billede arne_v Ekspert
14. november 2014 - 20:56 #7
Det var de jeg svarede paa i #1 og #2.
Avatar billede Peter22 Nybegynder
14. november 2014 - 21:09 #8
ja...tak for hjælpen
Avatar billede Peter22 Nybegynder
14. november 2014 - 21:10 #9
det vil sige at jeg ikke kan brug koden som jeg har vist dig ??
Avatar billede bvirk Guru
14. november 2014 - 23:34 #10
Vedr. 2, mere hvad end hvordan, måske ...
- anvendende B-tree: http://www.sanfoundry.com/java-program-perform-sorting-b-tree/

* smid 1. item i et b-træ
* med item fra nr 2 til n
    med  b-træ's search function
      sålænge item's dif til sum ikke findes
          insert item i b-trae
      ellers fundet
Avatar billede arne_v Ekspert
15. november 2014 - 02:37 #11
Umiddelbart har du ikke noget at bruge den quick sort kode til. Jeg foreslog at sortere som en del af #2 men der er indbygget funktionalitet i Java standard bibliotek til at sortere.
Avatar billede Peter22 Nybegynder
21. november 2014 - 22:23 #12
Kan du ikke give et eksempel på hvordan jeg kunne implementere det.. fordi jeg er helt væk... og jeg forstår ikke helt hvordan jeg skal løse problement
Avatar billede arne_v Ekspert
22. november 2014 - 00:08 #13
Du har ikke faaet den dobbelte for loekke til at virke?
Avatar billede Peter22 Nybegynder
22. november 2014 - 00:21 #14
nej det har jeg ikke :(
Avatar billede arne_v Ekspert
22. november 2014 - 01:49 #15
Hvordan ville du goere det i haanden hvis du havde N papir lapper med tal skrevet paa?
Avatar billede Peter22 Nybegynder
22. november 2014 - 11:53 #16
ved det ikke.. kan jeg ikke finde eksempler på nettet ??
hvis du ikke gider at hjælp mig
Avatar billede arne_v Ekspert
22. november 2014 - 15:55 #17
Jeg forsoeger faktisk at hjaelpe. Men at skrive et par stumper kode til dig som du ikke forstaar er ikke nogen rigtig hjaelp. Hele pointen med saadan en oevelse er jo at du skal laere noget.

Proev og tag 4 stykker papir og skriv 1, 2, 3 og 4 paa dem. Laeg dem paa bordet i tilfaeldig orden. Hvilke kombinationer af 2 stykker papir vil matche at summen af tallene er 5.

Jeg er sikker paa at du kan finde dem uden overhovedet at taenke over det.

Tricket er at taenke over det. Hvad goer du rent faktisk trin vist for at loese opgaven. Skriv det ned paa almindeligt dansk i punkt form.

Naar du har det saaa har du en algoritme!!

Derefter skal du have "oversat" algoritmenten fra dansk til Java.
Avatar billede Peter22 Nybegynder
22. november 2014 - 16:11 #18
det først jeg vil gør at jeg trækker et tal og så vil jeg løbe  listen array  igennem for at se om jeg kan finde et tal som til sammen giver 5
Avatar billede arne_v Ekspert
23. november 2014 - 01:19 #19
saa:

gaa gennem alle stykkerne en af gangen
    gaa gennem alle de andre stykker en af gangen
        check om sum er det oenskede

?

I Java bliver det til:

for(...) {
  for(...) {
      if(...) {
          ...
      }
  }
}
Avatar billede Peter22 Nybegynder
27. november 2014 - 21:48 #20
import java.util.concurrent.TimeUnit;
import com.google.common.base.Stopwatch;

public class sum
{
public static void main (String[] arg)
{
int  i = [1,2,3,4,5,6,7,8,9,10]
int sum = 0;
for ( int i =0 i < 10; i++  ){
system.out.println( sum" : " ")
}
for
if( sum < 10 ){
system.out.println( sum)
}
    int start= 1;
    Stopwatch data =Stopwatch.createStarted();
    while(start<=){
        System.out.println(sum(start));
        start++;
       
    }
    data.stop();
    System.out.println(data.elapsed(TimeUnit.MICROSECONDS) + " ms");
}
Avatar billede arne_v Ekspert
28. november 2014 - 01:34 #21
Den kode compiler ikke.
Avatar billede Peter22 Nybegynder
28. november 2014 - 09:13 #22
Det ved jeg godt.. Jeg vil hører om det var på rigtig måde jeg gør det på
Avatar billede MADOlsen Forsker
28. november 2014 - 09:29 #23
Har du overhovedet selv nogen som helst idé om, hvad den kode gør?

Det ligner ikke noget, der på nogen måde har noget med opgaven at gøre...
Avatar billede Peter22 Nybegynder
28. november 2014 - 10:00 #24
Ok.. Hvordan vil du løse opgaven ??
Mit spørgsmål var jeg kan bruge det til opgave
Avatar billede MADOlsen Forsker
28. november 2014 - 10:04 #25
Jeg ville løse det præcist som Arne foreslår i #19.
Avatar billede Peter22 Nybegynder
28. november 2014 - 11:33 #26
ok.. er det ikke det jeg gør
Avatar billede MADOlsen Forsker
28. november 2014 - 12:20 #27
Hvis vi lige der bort fra alle syntax-fejlene, så opretter du et int-array (i) med tallene fra 1 til 10, samt en int (sum) som du assigner værdien 0.
Så udskriver du vist nok noget med sum (som du lige har sat = 0) 10 gange i træk.

Hvis sum er mindre end 10 (og det er den, for den er jo stadig 0), så udskriver du den så igen.
   
Så opretter og starter du et stopwatch-object, hvorefter du kører et while-loop så længe start (som du lige har sat = 1) er mindre eller lig med.. Ingenting?
I dette while-loop prøver du at udskrive noget med sum og start, hvorefter du tæller start 1 op.

Når så konditionen ikke længere er opfyldt, så stopper du stopwatch'en, og udskriver antallet af mikrosekunder, den har kørt.

Hvordan skulle det på nogen måde løse den opgave, du har stillet???
Avatar billede Peter22 Nybegynder
28. november 2014 - 13:46 #28
public static int maxSubSum1( int [1,2,3,4,5,6,7,8,9,10 ] a )
{
int maxSum = 0;

for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;

for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
maxSum = thisSum;
}
return maxSum;
}
OK er det sådan i mener jeg skal lave det
Avatar billede MADOlsen Forsker
28. november 2014 - 14:09 #29
Det eneste den kode gør, er at lægge alle talene i arrayet sammen (på en meget besværlig måde).

Du har jo allerede i #18 forklaret, hvordan du vil gøre det, du mangler bare at omsætte det til kode.
Avatar billede Peter22 Nybegynder
28. november 2014 - 15:40 #30
for at gå gennem alle stykkerne en af gangen skal jeg brug for loop
så jeg skriver først
for ( int i = 0 ; i < i.lenght ; i++)

er det rigtigt ??
Avatar billede MADOlsen Forsker
28. november 2014 - 16:14 #31
i.length er forkert. Det skal være længden af dit array i stedet.

Og skal length i øvrigt også staves rigtigt ;-)
Avatar billede Peter22 Nybegynder
28. november 2014 - 16:30 #32
heheh ok..
det vil sige at jeg skal skrive

for (int i =0; i < 6 ; i++ )
Avatar billede Peter22 Nybegynder
28. november 2014 - 16:34 #33
nu er det her jeg ikke ved hvad jeg skal skrive kan du hjælp mig
Avatar billede MADOlsen Forsker
28. november 2014 - 20:02 #34
Det vil fungere, men kun hvis dit array har præcis 6 elementer.

Hvis du i stedet skriver

for (int i = 0; i < navnetPåDitArray.length; i++)

vil det fungere ligegyldigt hvilken længde dit array har.
Avatar billede Peter22 Nybegynder
28. november 2014 - 22:31 #35
ok.. men hvad skal jeg lave nu.. skal jeg lave en for loop mere
Avatar billede Peter22 Nybegynder
29. november 2014 - 17:01 #36
Er er der nogle som kan se hvad jeg har lavet forkert ??
eg er igang med at implementere O(n^2)

public class Sum {

    public static void main(String[] args) {
        // TODO Auto-generated method stub¨
       
        public int sum1(v){
        int sum[] = new int[10];
       
        for (int i = 0; i < sum.length; i++){
            int sum2 = i+ i;
   
        }
        for (int i = 0; i < sum.length; i++){
        if( sum[i] == v)
            return i;
        }
   
        }
    }

}
Avatar billede MADOlsen Forsker
01. december 2014 - 09:23 #37
Jeg har lige kommenteret på din kode.
Igen ser vi bort fra syntax-fejl (jeg har ikke pillet ved Java i ca. et halvt årti, så det er jeg nok alligevel ikke den rigtige til at rette).

public class Sum {

    public static void main(String[] args) {
        // TODO Auto-generated method stub¨
       
        public int sum1(v){  // Hvad er variablen v??
        int sum[] = new int[10]; // Du erklærer et array med længden 10, men du fylder intet i det
       
        // Du traverserer arrayet, men bruger ikke arrayets elementer til noget
        // (men du har jo heller ikke fyldt nogen elementer i det).
        // I stedet lægger du i sammen med i og gemmer resultatet i variablen sum2
        // (som du ikke tilgår senere).
        for (int i = 0; i < sum.length; i++){
            int sum2 = i+ i;
   
        }
       
        // Du traverserer igen arrayet, og tjekker om hvert enkelt element er lig med værdien af v.
        // Hvis den er det, så returnerer du elementets index.
        for (int i = 0; i < sum.length; i++){
        if( sum[i] == v)
            return i;
        }
   
        }
    }

}

Har du selv skrevet koden? Igen ser det ikke ud til at have noget som helst med den stillede opgave at gøre...

Så svaret på spørgsmålet:

"Er er der nogle som kan se hvad jeg har lavet forkert ??"

må være: stort set alt!
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester