Премини към съдържанието

Архивирана тема

Темата е твърде стара и е архивирана. Не можете да добавяте нови отговори в нея, но винаги можете да публикувате нова тема, в която да продължи дискусията. Регистрирайте се или влезте във вашия профил за да публикувате нова тема.

1click

Обяснение на малко код

Препоръчан отговор


Здравейте,
мъча се с един код, който намерих в интернет, но не го разбирам. Той е решение на тази задача:
Напишете програма, която намира максималната редица от еднакви
елементи в масив. Пример: {2, 1, 1, 2, 3, 3, 2, 2, 2, 1} -> {2, 2, 2}.

 

Може ли някой да ми разясни подробно, ред по ред какво прави кода?
 

Scanner input = new Scanner(System.in);
   int n;
   System.out.print("n=");
   n=input.nextInt();
   int[] array1=new int[n];
   int[] array2=new int[n];

   //Въвеждане на елементите на масива array1;
   for(int i=0;i<n;i++){
   System.out.printf("array1[%d]=",i); // динамична промяна на индекса на масива
   array1=input.nextInt();
   }

   //Проверка за max редица с еднакви елементи(от масива:array1);
   int start=1;
   int count=1;
   int bestCount=0,bestStart=0;

   for(int i=0;i<n-1;i++){
   if (array1==array1[i+1]){
   array2=array1;


   start=(i+1)-count;
   count+=1;

   if(count>bestCount){
   bestCount=count;
   bestStart=start;
   }

   }
   else {
   count=1;
   start=i+1;
   array2=0;
   }
   }
   System.out.println("Началото на редицата е от индекс:"+bestStart);
   System.out.println("bestCount="+bestCount);

   for(int i=bestStart;i<bestStart+bestCount;i++){
     System.out.print(" " + array1);

   }

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Здравейте, Написал съм коментарите inline в кода. Надявам се, да хвърлят някаква светлина върху логиката на кода:  

Scanner input = new Scanner(System.in);        int n;        System.out.print("n=");        n=input.nextInt();        int[] array1=new int[n];        int[] array2=new int[n];        //Въвеждане на елементите на масива array1;        for(int i=0;i<n;i++){			System.out.printf("array1[%d]=",i); // динамична промяна на индекса на масива			array1[i]=input.nextInt();        }        //Проверка за max редица с еднакви елементи(от масива:array1);        int start=1;        int count=1;        int bestCount=0,bestStart=0;		//Идеята на долния код е намиране на максимално дълга подредица от еднакви числа в дадената подредица. 		//В масива array2 ще се съхрани всички редици от последователни еднакви числа от масива array1. Например:		//array1 = {1, 2, 2, 4, 5, 6, 6, 6, 6, 7}. След като се изпълни алгоритъма, 		//array2 = {0, 2, 2, 0, 0, 6, 6, 6, 6, 0} - т.е. на същите индекси на който са елементите от всички подредици от еднакви последвателни числа.		//Индексите bestCount и bestStart се явяват съответно дължината на най-дългата такава редица, и от кой индекс на масивите array1 и array2                 //започва тя.        for(int i=0;i<n-1;i++){			//Ако имаме два еднакви съседни елемента			if (array1[i]==array1[i+1]){				//Попълни стойността на съответната позиция в изходния масив array2				array2[i]=array1[i];				//Коригирай стартовия индекс на текущо анализираната подредица от еднакви числа.				//Забележка: start индекса няма да се промени като стойност реално, в случаите, когато все още имаме еднакви съседни елементи,				//защото въпреки, че i се увеличава с 1 на всяка итерация, count-а също се е увеличил (от предната итерация) и реално start                                 //не се променя !!!				start=(i+1)-count;				//Увеличи с едно броя на елементите от текущата подредица.				count+=1;				//Ако текущата дължина на подредицата е по-голяма от най-голямата дължина, намерена досега				if(count>bestCount){					//Тогава текущата редица е решението ЗА МОМЕНТА ! Присвои данните от кой индекс започва и колко е дълга,					bestCount=count;					bestStart=start;				}				//ЗАБЕЛЕЖКА: В горния if ще се влиза дори и във случаите, когато все още анализираме текущата подредица от еднакви числа.			} else {				//Ако пък текущия елемент и съседа му са различни по стойност, занули елемента за съответния индекс на array2, коригирай                                 //start да отиде на следващия елемент и count да е 1.				//Забележка: Ако имаме абсолютно разнороден масив, програмата би трябвало да върне редица, изградена само от предпоследния                                 //елемент на array1				count=1;				start=i+1;				array2[i]=0;			}        }        System.out.println("Началото на редицата е от индекс:"+bestStart);        System.out.println("bestCount="+bestCount);		//Изведи търсената редица от array1        for(int i=bestStart;i<bestStart+bestCount;i++){            System.out.print(" " + array1[i]);        }

Бих искал само да уточня няколко неща за въпросния код:

1) Кода намира подредица от елементи, които са еднакви по стойност и съседни по локация в масива. Това ще рече, че ако имаме входния масив {1,2,2,2,3,2} то решението на задачата ще е {2,2,2} а не {2,2,2,2}. Ако това е търсения отговор, значи всичко е ОК, но ако отговора, който се търси е втория, горния код трябва да претърпи промяна (допълнителен вложен цикъл + 1-2 локални променливи). 

2) В момента както е, кода търкаля всички елементи, от масива. Може да се отпимизира, като се добави един флаг (boolean), който да проверява дали дължината на текущо най-добрата подредица (bestCount) е по-голяма от броя на останалите елементи (n - i) на масива array1. В този случай, можем ако в момента сме на редица от еднакви елементи, да довършим анализа на редицата и да прекъснем изпълнението на търсещия цикъл, или ако не сме в процеса на анализ на някоя редица, направо да прекъснем и да изведем най-добрата такава. Това би спестило в най-оптималния случай (n/2) - 1 операции по проверка (търсената най-голяма подредица е съставена от първите (n/2)+1 числа), а в най-лошия случай ще си останем с n проверки (т.е. разнороден масив)

3) Кода се изпълнява за линейно време и не мисля, че може да се свали до log(n) или нещо от тази скала. За пренареждане и модифициране на масива и дума не става, защото на нас ни е необходим в изначалния му вид, където позицията на елементите има значение.

 

Поздрави !

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.