JS [Arrays] зад.4


4

 Как се справяте с тази задача?

4.Write a script that finds the maximal increasing sequence in an array. Example:
{3, 2, 3, 4, 2, 2, 4} à {2, 3, 4}.
 
Аз от доста време си бия главата и не се получава. Ето ми и кода:
        var array = [8,5,6,7,5,8];        
        var start = 0;
        var len = 1; 
        var bestStart = 0;
        var Bestlen = 0; 
        var seq = [];    
        for ( i = 0; i < array.length; i++ ){
        
            if ( array[i] < array[i+1] ){
              len++;
            } else {
              len = 1;
              start = i;
            };
              
            if ( len > Bestlen ){
                bestStart = start;
                Bestlen = len;
             };
        };
    
        for ( i = bestStart; i < bestStart + Bestlen; i++ ){
           seq.push(array[i]);
           
        };
        console.log(seq);
 
Моля, дайте някакви идеи!
 

 




Отговори



4

Ами аз съм я решавал на C# и идеята ми бепе следната.

  1. Декларраме масива
  2. Правим променлива с дължината на последващите елементи
  3. Променлива с последния проверен елемент
  4. Променлива с най-добрата дължина засега
  5. След това обхождаме масива, като преглеждаме текущия и следващия елемент(i+1).
  6. Ако разликата им е равна на единица увеличаваме дължината(точка 2), ако не я връщаме на началната и стойност от единица.
  7. Ако текущата дължина е по-голяма от най-добрата записана досега, правим текущата най-добра и увеличаваме последния елемент с единица.
  8. Принтвам масива от най-малката стойност на поредицата, до най-голямата

Или просто ето ти кода на C# за да го проследиш: http://pastebin.com/DsdFY8md

Така я реших, аз. Доста сходно на твоя подход. Не казвам, че е най-правилния начин, но все пак се надявам да ти помогне. :)

Поздрави,

Стоян


от kirov (4821 точки)


0
Имаш проблем с граничния случай. При целева редица, завършваща с последния елемент). По-надолу имам пост. Надявам се инфото да е полезно. :)

от Velidar (1099 точки)

0
и аз реших задачата като @kirov. Няма проблем с последния елемент, ако цикъла е от 0 до length -1. End се намира лесно, а . bestStart така и не успях да намеря. Искам да попитам обаче нарастваща редица не значи ли поредна, нарастваща с 1 само.

от ilgeo (115 точки)



2
Задачата не е ли подобна на 3-та?
Още съм начинаеща и ми е трудно да разследвам грешките в чуждия код, но на пръв поглед: Bestlen не трябва ли да започва с малка буква напр.

от svetlaz (269 точки)


2

Излизаш от масива array (трябва да е от 0 до array.length()-1 )
И също така в else-a трябва да изглежда така:
else 
{

    if len Bestlen )

   {
                bestStart start;
                Bestlen len;
   };
              len 1;
              start i;
};

Грешката е, че нулираш start и len преди да им придадеш стойността като най-добра.


от Subo_Rusev (1389 точки)


2

Добре ти е казано по-горе. За да работи, просто вкарай условието за нова целева редица преди това, което е вече в else-a. Когато не осъзнаваш защо нещо не става, дебъгвай JavaScripta с браузърите и/или си разписвай логиката цялостно. 

Относно граничния случай, при който имаш най-дълга редица в края.
 
Излизаш от масива, само заради онова условие, в което имаш array[i+1], което при последната итерация гледа извън него и сравняваш единствено с undefined. Можеш наистина, вместо до дължината, да продължаваш цикъла до нея -1. Така няма да излезеш от него... но ще имаш проблеми след това.
Започвай цикъла от 1 (= 1) и промени if array[iarray[i+1] ) на това: if array[i-1array[i] )
Има и още нещо, обаче. Трябва да изнесеш условието, за нова най-дълга редица, и след цикъла. Иначе НЕ се стига до него, един последен нужен път - цикълът е приключил.
 

от Velidar (1099 точки)


0
Благодаря за насоките! Но все още ми е трудно!! До преди един-два месеца си нямах и понятие от Javascript, съвсем начинаещ съм. Разбирам логиката на масиви и цикли, но ми е трудно все още да ги комбинирам, нямам този опит. Лошото е, че на лекциите обясняват най-елементарни примери, хубаво, това е за да се разбере основата /няма лошо/ но, дайте и пример за по-сложна ситуация /няма такова нещо/ и аз изчетох Google! Без очи останах! Май се отплеснах, извинявай!

от Plamen_Monev (45 точки)

0
Няма проблеми. Истината е, че всичко е до яко блъскане. Така е, не е лесно. Напълно нормално е да "изчиташ гугъл" и да се сблъскваш с проблеми. Просто друг начин няма. Там е работата, че колкото и да се обяснява на лекцията, резултатът ще е минимален, защото става единствено с много решаване. Всеки човек сам си достига до алгоритмично мислене, а на лекция е много трудно да бъде даден точен модел. Начина е много решаване, сблъскване с проблеми и разрешаването им с много пот (личен опит, не че съм кой знае колко напред...). И не трябва да те притеснява, когато не работи нещо! Даже е добре да се заиграваш, да се питаш "това защо не би работило така", да го тестваш, да разбираш кое не би било подходящо и в крайна сметка да успяваш. Дали мислиш, че тези насоки дето ги написах (относно задачата), ги видях веднагически и осъзнах, че са правилни? Трябваше да тествам и си поиграх с няколко варианта. Иначе пак казвам. Когато срещаш спънки в собствените си решения и се чудиш защо не се случва очакваното, проследявай си логиката стъпка по стъпка. Разписвай си, ако трябва, какво се случва на всяка стъпка. Човек така се учи. Бавничко е, но се постига резултат, а и е нужно.

от Velidar (1099 точки)



2

И аз се озорих доста, но накрая имам работещ алгоритъм:

 

            function maxIncreaseSeqence(){
                var data = document.getElementById("data").value;   // this is the initial data
                var arr = data.split(",");                          // here we create the array we'll work with
                var repeat = 1;                                     // this variable will count the repetition of a specific fulfilled condition(s)
                var count;                                          // this variable will define where all the repetitions start
                var countMaxStart = 0;                              // this variable will define the start of the maximal increasing sequence
                var countMaxEnd;                                    // this variable will define the end of the maximal increasing sequence
                var repeatMax = 0;                                  // this variable will count the greatest repetition of a specific fulfilled condition(s)
                var seq = [];                                       // this would be the maximal increasing sequence
                for (i=0; i<arr.length; i++){                       // this loop defines arr[countMaxStart] and repeatMax
                    count = i + 1;
                    if (arr[parseInt(i)+1] == parseInt(arr[i])+1){ 
                        count = count - repeat;
                        repeat++;
                        if (repeat >= repeatMax) {
                            repeatMax = repeat;
                            countMaxStart = count;
                        } 
                    }
                    else {
                        count = 1;
                        repeat = 1;            
                    }                                     
                }
                countMaxEnd = parseInt(arr[countMaxStart])+parseInt(repeatMax);  // here we can calcutale the value of countMaxEnd
                for (n=parseInt(arr[countMaxStart]);n<countMaxEnd;n++){          // this loop will create seq = []
                    seq.push(n);
                    seq.join(",");
                }
                /** 
                You can debug by using these three alert messages:
                alert("arr[countMax] = " + arr[countMaxStart]);
                alert("repeatMax = " + repeatMax);
                alert("seq = " + seq); **/
                
                alert("The maximal increasing sequence in this array is "+ seq); // finally the result is being displayed in an alert box.
            }



1

Ето и моето решетие

http://jsfiddle.net/siropo/Vakk6/

След като хванах най-после :) идеята как да изкарам всички повтарящи се по дължина еднакви числа в масива днес не беше толкова трудно да го барна да вади всички повтарящи се по дължина нарастващи с 1 числа.

Eдит: малък ъпдейт който да работи и с отрицателни числа, че преди това не ставаше. 

v.1.1 - http://jsfiddle.net/siropo/Vakk6/1/


от Viktor_Ivanov (2505 точки)


0
С уважение към труда на всички и с благодарност за споделените кодове се престрашавам да питам все пак защо трябва да е толкова сложно?

от ilgeo (115 точки)

0
@dreamer - Колега, лично аз не ти разбрах въпроса?

от georgi.s.yankov (6219 точки)



3

Ето и моето решение - ако може да е полезно с нещо на някого и ако някой иска да помогне с критика:

            var theArr=new Array();
            var addrArr=new Array();
            var lenArr=new Array();
            var number;
            var start=0;
            var len=1;
                        
            
            do{
            number = prompt("Enter numbers here:");
             if (number == "" || number == null)
             break;
             else{
                theArr.push(parseInt(number));    
             }
             
            }
            while(number!=null );
        
            for ( var i = 1; i<=theArr.length; i++){
                    var prev=theArr[i] - 1;
                    if(theArr[i-1]=== prev){
                        start=i;
                        len++;
                    }
                    else{
                        lenArr.push(len);
                        addrArr.push(start);
                        start=0;
                        len=1;
                    }
                }
                    var seqArr=new Array();
                    var max=Math.max.apply(null,lenArr);
                    
                for(i=0; i<lenArr.length; i++){
                    
                    if(max>1){
                        if(max===lenArr[i])
                        for(var p=0; p<max; p++){
                                  seqArr.unshift(theArr[addrArr[i]-p]);


                            }
                        }
                    else{
                            seqArr=["There is no second sequent number"]
                    }
                }
                console.log("The Array is : " + theArr + ";  The longest sequence(s) is/are : " + seqArr);


от svetlaz (269 точки)


1
Аз още не съм я решила тази задача. Намирам кои са числата, но имам проблем с това да ги изкарам.
http://jsbin.com/awakuv/1/edit (с конзола)
Изреждат се без последното, независимо дали е гранично или не. Решението на Киров работи, но честно казано не разбирам начина, по който ги принтва с последния цикъл.

от rnikiforova (1198 точки)


0
Ето едно позакъсняло решение и от мен:
http://pastebin.com/JNBFj7Lg
Правя проверка за последният елемент от редицата - за което питаше колежката Никофорова.

от ekostadinov (200 точки)


2

Ето и моето решение.

http://jsbin.com/iBoXIvo/1/edit?html,console

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title>HW 4</title>
</head>
<body>
    <script>

        var arr = [0, 1, 2, 0, 1, 2, 3, 4, 5, -2, 0, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, , -2,7, 8, 9, 10, 5, 6, 7, 8, 9];
        console.log(arr.join());
        var arrMAX = [arr[0]];
        var arrNEXT = [arr[0]];
        var count = 1;

        for (var i = 0; i < arr.length - 1; i++) {
            if (arr[i] < (arr[i + 1])) {
                arrNEXT.splice(arrNEXT.length, 0, arr[i + 1]);
                count += 1;
                if (arrMAX.length < count) {
                    arrMAX = arrNEXT;
                }
            } else {
                arrNEXT = [arr[i + 1]];
                count = 1;
            }
        }
        console.log("arrMAX = " + arrMAX.join("|"));
    </script>
</body>
</html>
 


от bstaykov (528 точки)


1

Ето и моето решение на задачата с обяснени на моята логика: http://pastebin.com/N4GxXNRH .

Ако имате мнение споделете. wink


от Dodko (165 точки)