Ushbu funktsiyani yanada "oqlangan" C ++ qilish

Ushbu rekordiv funktsiyani yanada oqilona qilish uchun baribir bormi? Funktsiyani bajarishni istayman, shuning uchun takrorlanadigan kod yo'q.

int findMaximumValue(int list[], int first, int last)
{
    if (first == last)
        return list[first];
    else {
        if (list[first] > findMaximumValue(list, first + 1, last))
            return list[first];
        else
            return findMaximumValue(list, first + 1, last);
    }
}
1
Ha, buning o'rniga men uni yozaman.
qo'shib qo'ydi muallif kekstorm, manba
Yo'q, bu noto'g'ri murakkablik bor.
qo'shib qo'ydi muallif n.m., manba
Funktsiya ishlashi kerakmi? So'ngra kodni tekshirishni xohlasangiz, codereview.stackexchange.com manziliga yozing.
qo'shib qo'ydi muallif Some programmer dude, manba
Stack Overflow kodlash muammolarini hal qilish uchun, bu savolni mavzu tashqari yopish uchun ovoz beraman. Ish kodini takomillashtirish bo'yicha maslahat uchun Kodni tekshirish o'rniga foydalaning.
qo'shib qo'ydi muallif Toby Speight, manba

6 javoblar

Darhaqiqat, darhol paydo bo'ladigan ikki narsasi mavjud:

  • Birinchi qaytish else -ni ortiqcha bajargani uchun agar ... keyin esa ... paradigmini qaytarib olmaslik kerak.
  • Ikkinchidan, faqat bir marta ishlatilgan chaqiriqni amalga oshirish. (bu o'zgaruvchan emas).

Ushbu o'zgarishlarni amalga oshirish sizga quyidagi narsalarni beradi:

int findMaximumValue(int list[], int first, int last) {
   //List has one item, return it.

    if (first == last)
        return list[first];

   //Get largest of all but first element in list.

    int maxOfAllButFirst = findMaximumValue(list, first + 1, last);

   //First is larger than all those others, return it.

    if (list[first] > maxOfAllButFirst)
        return list[first];

   //Otherwise it's largest from the others.

    return maxOfAllButFirst;
}

Shuni aytib o'tishim kerakki, retsursiyaning yaxshi bajarilishi algoritmlar uchun hal etish maydoni tezda kamayadi (masalan, har bir recursive chaqiruvdagi qolgan yechim maydonining yarmini olib tashlang).

Yechim bo'shlig'i asta-sekin kamayib boradigan (masalan, asosan, chiziqli qidirish) rekviziondan foydalanish eng yaxshi g'oya emas. Tail call optimallashtirish qilolmaydigan bo'lsa, siz bo'shashtiriladigan joydan ancha tez ishlatasiz.

Boshqacha qilib aytganda, ushbu algoritmini yanada oqilona qilishning eng yaxshi usuli uni yinelemeli biridan yineluvchi :-) ga aylantirishdan iborat

1
qo'shib qo'ydi
Rahmat, men aynan shu narsani qidiryapman. boshqa - men qutulishga harakat qilaman!
qo'shib qo'ydi muallif kekstorm, manba
Va ha, bu ikkilik qidiruv va boshqalarga linear qidirish hozirda nimani o'rganyapman. Odatda lineer rejimda 1024 o'rniga maqsadni qidirib topish mumkin. Bu chiziqli va ikkilik kodlangan usul bilan taqqoslash uchun oddiy topshiriqdir. Mening ishimda ro'yxat hajmi 100 dollarni tashkil etadi, shuning uchun u juda yomon emas.
qo'shib qo'ydi muallif kekstorm, manba

Agar siz standart kutubxonadan funktsiyalardan foydalanishga ruxsat bersangiz, funksiyani soddalashtirishingiz mumkin:

int findMaximumValue(int list[], int first, int last)
{
    if (first == last)
        return list[first];

    return std::max(list[first], findMaximumValue(list, first + 1, last));
}

Agar standart kutubxonadan biron bir funktsiyadan foydalanishga ruxsat etilmagan bo'lsa, max funktsiyasini yozing va undan foydalaning.

1
qo'shib qo'ydi

Ha, siz ikkinchi elementdan oxirgi elementga hisoblashingiz mumkin, uni o'zgaruvchiga saqlashingiz va keyin uni ishlatishingiz mumkin:

int findMaximumValue(int list[], int first, int last)
{
    if (first == last)
        return list[first];
    else {
        int maxFromSecond = findMaximumValue(list, first + 1, last);
        if (list[first] > maxFromSecond)
            return list[first];
        else
            return maxFromSecond;
    }
}

Yoki sizning funktsiyangizni qisqartirish uchun max (int, int) funktsiyasidan foydalanishingiz mumkin:

int findMaximumValue(int list[], int first, int last)
{
    if (first == last)
        return list[first];
    else
        return max(list[first], findMaximumValue(list, first + 1, last));
}
0
qo'shib qo'ydi

Sizning funktsiyangizdan voz kechish va ushbu standart algoritmni ishlatish uchun:

std::max_element(list, list + len);

http://www.cplusplus.com/reference/algorithm/max_element/

yoki ro'yxatni tartiblashtirish:

  int myints[] = {32,71,12,45,26,80,53,33};
  std::vector myvector (myints, myints+8);              //32 71 12 45 26 80 53 33

  std::sort(myvector.begin(), myvector.end(), std::greater<>()); //sort descending

  return *(myvector.begin());
0
qo'shib qo'ydi

Eng oqlangan kod;)

int findMaximumValue(void* list, int nextIndex, int last, int sizeofelem)
{
    int result;
    __asm {  
          push eax
          push ecx  
          push esi
          push edi       
          mov eax, nextIndex
          mov ecx, eax
          mul sizeofelem      
          mov esi, list       
          add esi, eax
          mov edi, esi
next:                     
          cmp ecx, last
          je  stop
comp: 
          add esi, sizeofelem
          inc ecx
          mov eax, [edi]
          cmp eax, [esi]          
          jl setgrte
          jmp next                
setgrte:  
          mov edi, esi
          jmp next
stop: 
          mov eax, [edi]
          mov [result], eax
          pop edi
          pop esi           
          pop ecx                                 
          pop eax
    } 
    return result;
}
//.....
int res = findMaximumValue((void*)&arr, lov, hiv, sizeof(int));
0
qo'shib qo'ydi

Buning muqobilligi, keyingi = 1, oxirgi = ro'yxati va listning birinchi elementi sifatida currMax

int findMaximumValue(int list[], int nextIndex, int last, int currMax)
{
    if (nextIndex == last)
        return currMax;

    int max = list[nextIndex] > currMax ? list[nextIndex] : currMax;
    return findMax(list, ++nextIndex, last, max);
}
0
qo'shib qo'ydi