Problem Z Algorytmem - Sprawdzenie Czy Tablice Sa Anagramami

[Beereq]

Witajcie moi mili!

 

Potrzebuję pomocy z algorytmem, może przejdę od razu do rzeczy:

 

 

Algorytm ma sprawdzać, czy dwie tablice są anagramami np. [1,2,3,4] i [2,3,1,5] nie są, ale np. [1,2,3,4] i [2,3,1,4] są. (tablice muszę być takie, aby przestawiając elementy w jednej z nich otrzymać drugą).

 

 

W skrócie mój plan działania:

 

1. Wprowadzenie danych

2. Sprawdzenie, czy długość (ilość liczb) w tablicach x i y jest taka sama.

3. Posortowanie tablic (np. w kolejności rosnącej)

4. Sprawdzanie element po elemencie

 

 

Doszedłem do czegoś takiego: (powiedzmy, że to Pascal)

 

 

A,B to tablice jednowymiarowe

i oznacza iterację wiersza tablicy (A lub B)

w1, w2 to liczba wierszy (elementow) tablicy odpowiednio A/B

asort, bsort - zmienne pomocnicze do sortowania bąbelkowego

 

 

Pomijając już wprowadzenie danych i deklarację zmiennych wymyśliłem coś takiego

 

 

while w1=w2 dobegin  for (i=0 to w1-1) && (i=0 to w2-1) do  if A[i] > A[i+1] then	begin	asort:=A[i+1];	A[i+1]:=A[i];	A[i]:=asort	end;  if B[i] > B[i+1] then	begin	bsort:=B[i+1];	B[i+1]:=B[i];	B[i]:=bsort	end;  for (i=0 to w1) do  if A[i]=B[i] then  wyświetl("Tablice sa anagramami")end;else wyświetl("Tablice nie sa anagramami")

 

Potrzebuję opinii czy to ma szansę działać, co jest ok a co jest nie ok i czy można zrobić to prościej, tak żeby zmniejszyć złożoność obliczeniową. (stosując quicksort?)

 

Docelowo ma to być zapisane jako:

 

Preferowany język C; proszę nie podawać głównej funkcji main, operacje we/wy (cout, printf, cin, scanf) zastąpić należy przez:

wyswietl("tekst"), wyswietl(a), pobierz(a); proszę nie przysyłać kodu wynikowego programu (*.exe); proszę nie używać instrukcji: goto, exit, break)

Jest to bardzo pilne...

[shooter]

Napisane zostało, że preferowany język: C. Nie znaczy to, że obligatoryjny.

 

Java - 2 minuty pisania

 

import java.util.*;public class Anagram {		public static boolean areAnagrams(List<? extends Comparable> list1, List<? extends Comparable> list2){		Collections.sort(list1);		Collections.sort(list2);		return list1.equals(list2);	}	       //test	public static void main(String... args){		List<Integer> list1 = new LinkedList<Integer>();		List<Integer> list2 = new LinkedList<Integer>();		list1.add(1);		list1.add(3);		list1.add(5);				list2.add(5);		list2.add(1);		list2.add(3);				System.out.println(areAnagrams(list1, list2));        }}

Co do uzytego algorytmu sortującego:

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

 

Wątpię żebyś napisał to lepiej.

 

Banał.

Edytowane 21 Stycznia 2010 przez shooter

[Beereq]

OK, dzięki za zainteresowanie tematem...

 

Ale obawiam się, że nie zrobię tego w javie bo nic a nic nie kumam, a jak mnie o coś zapytają to będzie tylko "yyyyy, działa" :P

 

Wolałbym C lub Pascala :>

[moe]

C# jak chcesz

static List<int>lista=new List<int>();		 static List<int> lista2 = new List<int>();		 static bool check;		 static void Main(string[] args)		 {			 lista.Add(1);			 lista.Add(0);			 lista.Add(2);			 lista2.Add(0);			 lista2.Add(1);			 lista2.Add(2);			 if (lista.Count == lista2.Count)			 {				 lista.Sort();				 lista2.Sort();				 check = lista.SequenceEqual(lista2);			 }			 Console.WriteLine(check);			 Console.ReadKey();		 }

a jak chcesz byc 'pro' to implementujesz interfejs IComparer

Edytowane 21 Stycznia 2010 przez moe