Implementacja sortowania przez zliczanie

rat12

2013-10-21T21:07:23+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 20

0

Witam.
Mam do zrobienia zadanie o treści:
Na wejściu danych jest n ( 1≤ n≤ 100) różnych liczb N+z przedziału [1,k] ( 1≤k≤150). Zaimplementuj algorytm(o możliwie najniższym koszcie czasowym), który wykorzystując zadane liczby, generuje zbiory 2-elementowe {x,0cm">y} spełniające własność x+y<=k.
Każdą liczbę należy użyć dokładnie jeden raz. W przypadku, gdy dla zadanej 0cm">wartości x nie można już znaleźć takiej liczby y, by spełniona była powyższą własność, należy utworzyć zbiór 1-elementowy {x}. Zadanie polega na znalezieniu możliwie najmniejszej ilości tego typu zbiorów.

Utworzyłem plik .txt oraz na wejście podałem n=8 oraz k=140 a liczby do posortowania to 60 70 80 56 67 78 81 68.Niżej umieściłem to co udało mi się stworzyć dane w .txt podałem w 1 linii więc na pewno zostały wszystkie zaczytane do strumienia lecz niestety nie działa podczas kompilacji wyrzuca mi:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 60
at zad2.sort.main(sort.java:33)
i nie wiem już co mam zrobić w tym momencie.

Kopiuj

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class sort {

    public static void main(String[] args) throws FileNotFoundException {
        // TODO Auto-generated method stub
String pomoc[] = null;
        
        File file = new File("1.txt");
        Scanner in = new Scanner(file);
        
        String dane = in.nextLine();
        pomoc = dane.split(" ");
        in.close();
        int j=2;            
int n = Integer.parseInt(pomoc[0]);    
//int o = Integer.parseInt(pomoc[1]);
 int[] T = new int[n];
 int[] Tp = new int[n];
 int c,k;
    for(int i=0;i<n;i++)
    {
        T[i]=Integer.parseInt(pomoc[j]);
        j++;
    }
    for(int i=0;i<n;i++)
        Tp[i]=0;
    for(int i=0;i<n;i++)
        Tp[T[i]]++;
    c=1;
    for(int i=0;i<n;i++){
        if (Tp[i]>0)
            for(k=1;k<Tp[i]+1;k++)
                T[c]=i;
                c++;
    }
    }
    
    }

dodanie znacznika <code class="java"> - fp

garai

2013-10-21T21:49:29+02:00

Rejestracja: dni
Ostatnio: dni

0

niezły śmietnik :) sformatuj kod...
na pewno masz złe pętle, po co tworzysz tablicę, której wielkość jest równa pierwszej sczytanej liczbie a później po niej iterujesz
a poza tym Twój kod w ogóle nie ma pokrycia z treścią zadania

_13th_Dragon

2013-10-21T22:48:30+02:00

Rejestracja: dni
Ostatnio: dni

2

Kopiuj

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class sort
  {
   public static void main(String[] args) throws FileNotFoundException
     {
      Scanner in=new Scanner(new File("1.txt"));
      int n=in.nextInt(),max=0;
      int[] T=new int[n];
      for(int i=0;i<n;++i) max=Math.max(max,T[i]=in.nextInt());
      int[] S=new int[max+1];
      for(int i=0;i<n;++i) ++S[T[i]];
      for(int p=0,i=0;i<=max;++i) while(S[i]-->0) T[p++]=i;
      for(int i=0;i<n;++i) System.out.print(T[i]+" ");
     }
  }

rat12

2013-10-21T23:21:38+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 20

0

_13th_Dragon napisał(a):

Kopiuj

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class sort
  {
   public static void main(String[] args) throws FileNotFoundException
     {
      Scanner in=new Scanner(new File("1.txt"));
      int n=in.nextInt(),max=0;
      int[] T=new int[n];
      for(int i=0;i<n;++i) max=Math.max(max,T[i]=in.nextInt());
      int[] S=new int[max+1];
      for(int i=0;i<n;++i) ++S[T[i]];
      for(int p=0,i=0;i<=max;++i) while(S[i]-->0) T[p++]=i;
      for(int i=0;i<n;++i) System.out.print(T[i]+" ");
     }
  }

Twój skrypt działa za wyjątkiem jednej rzeczy a mianowicie w .txt deklaruje wartości n=8 i k=140 obie te wartości mają być poza sortowaniem o skrypt wyłapuję mi wartość 140. I odpowiadając na pytanie kolegi wyżej. Mój kod przedstawiał część zadania a mianowicie sortowanie przez zliczanie(taki miał być) dopiero potem miałem miałem zająć się tworzeniem zbiorów.Dodatkowo

Kopiuj

 
int n = Integer.parseInt(pomoc[0]);    
int o = Integer.parseInt(pomoc[1]);

ta część miała za zadanie wyłapanie ze strumienia wartości n i k oraz przypisanie ich do int a żeby na koniec wynik móc wstawić do pliku .txt.

_13th_Dragon

2013-10-21T23:40:59+02:00

Rejestracja: dni
Ostatnio: dni

2

Kopiuj

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class sort
  {
   public static void main(String[] args) throws FileNotFoundException
     {
      Scanner in=new Scanner(new File("1.txt"));
      int n=in.nextInt(),k=in.nextInt(),max=0;
      int[] T=new int[n];
      for(int i=0;i<n;++i) max=Math.max(max,T[i]=in.nextInt());
      int[] S=new int[max+1];
      for(int i=0;i<n;++i) ++S[T[i]];
      for(int p=0,i=0;i<=max;++i) while(S[i]-->0) T[p++]=i;
      for(int i=0;i<n;++i) System.out.print(T[i]+" ");
     }
  }

rat12

2013-10-28T19:00:44+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 20

0

Witam jeszcze raz pogram dokończyłem i lata w sumie bez problemowo lecz muszę napisać jego alternatywę która w musi (w zależności od tego jak napisałem obecny kod) być troszkę wolniejsza bądź szybsza. Mianowicie mam dodany tam licznik operacji elementarnych obecny wynik to 103 czy da się go poprawić?

Kopiuj

package zad2;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

 
public class sort
{
public static int d=0;

   public static void main(String[] args) throws FileNotFoundException
     {
      Scanner in=new Scanner(new File("1.txt"));
      int n=in.nextInt();
      int k=in.nextInt();
      int max=0;
      int[] T=new int[n];
      for(int i=0;i<n;++i) 
      {
          max=Math.max(max,T[i]=in.nextInt());
              d++;
      }
      int[] S=new int[max+1];
      for(int i=0;i<n;++i) 
      {
          ++S[T[i]];
                  d++;
      }
      for(int p=0,i=0;i<=max;++i) 
          {
          while(S[i]-->0) 
          
              T[p++]=i;
                  d++;
          }
      List<String> lista = new ArrayList<String>();
      String a;
      for(int p=n-1,i=0;i<n;i++)    
      if(i==p)
      {
          a=""+T[p];
          lista.add(a);
              d++;
          break;
      }
      else    
          if(T[i]+T[p]<=k)
          {
              a=""+T[i]+" "+T[p];
              lista.add(a);
                  p--;        
                  d++;
          }
          else 
              if(T[i]+T[p]>k)
              {
                  a=""+T[p];
                  lista.add(a);
                  p--;i--;
                  d++;
              }
      PrintWriter zapis = new PrintWriter("2.txt");
        zapis.println("n="+n+" k="+" "+k+"ilość zbiorów"+"="+lista.size()+"zbiory:"+lista+"ilość operacji elementarnych:"+d);
        zapis.close();
          in.close();
     }
  }