Найти максимальный элемент в массиве (делением пополам)

@correcеt · Регистрация: 20.04.2011

Author24 — интернет-сервис помощи студентам

Всем привет!
подскажите такой момент:
Найти максимальный элемент в массиве ai (i=1, , n), используя соотноше-ние (деления пополам) max(a1,, an) = max[max(a1,, an/2), max(an/2+1, , an)].

Делаю так:

C++ (Qt)

//---------------------------------------------------------------------------
#include <stdlib.h>
#include <math.h>
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <vcl.h>
#pragma hdrstop
 
//---------------------------------------------------------------------------
 
#pragma argsused
            double _max;
 double maxr(double *a,int n);
int main(int argc, char* argv[])
        {
double a[10]={2,1,4,5,7,8,1,6,9,10};
double r=maxr(a,4);
printf("maximum=%Lf\n",r);
getch();
 
}
double maxr(double *a,int n)
      {
if(n==1)
return a[0];
if(n==2)
return max(a[0],a[1]);
double max1= maxr(a,n/2);
double max2=maxr(a+n/2,n/2);
return max(max1,max2);
}

получаю это:

Найти максимальный элемент в массиве (делением пополам)

@volvo · 25.03.2016, 11:57

C++

1	printf("maximum=%f\n",r); // выдает 5, как и ожидалось

@k399et · 25.03.2016, 14:48

Сообщение от correcеt

C++

 {
if(n==1) return a[0];
if(n==2) return max(a[0],a[1]);    // ИЗБЫТОЧНОЕ УСЛОВИЕ.
double max1= maxr(a,n/2);
double max2=maxr(a+n/2,n/2);    // ??? ОШИБКА.
return max(max1,max2);
}

Такая схема корректно работает только на размере массива с количеством элементов равным степени двойки.
Чуть более элегантное и корректное решение:

C++

double maxr(double *a,int n);
int main( int argc, char* argv[])
{
double a[] = {1,4,2,3,5,6,7,8,9,10};
double r = maxr( a, sizeof(a)/sizeof(double) );
 
// PRINT( r );
}
 
 
double max( double _a1, double _a2 ) { return (_a1 >_a2 ) ? _a1 :_a2; }
 
double maxr( double *a, int n )
{
return (n==1) ? a[0] : max( maxr(a,n/2), maxr( a+n/2,n/2+(n&1) ) );   // +(n&1) существенное замечание. 
}

@correcеt · 28.03.2016, 09:13 **[ТС]**

k399et, что-то не очень понятно что выводит ваш элегантный пирмер,ибо при запуске у меня консоль закрывается,system("PAUSE"); не помогает

@k399et · 28.03.2016, 10:00

C++

double max( double _a1, double _a2 ) { return (_a1 >_a2 ) ? _a1 :_a2; }
 
int _tmain(int argc, _TCHAR* argv[])
{
double maxr(double *a,int n);
 
double a[] = {1,4,2,3,5,6,7,8,9,10};
double r = maxr( a, sizeof(a)/sizeof(double) );
 
    printf( "r = %f", r );
    getch();
}
 
double maxr( double *a, int n )
{
return (n==1) ? a[0] : max( maxr(a,n/2), maxr( a+n/2,n/2+(n&1) ) );   // +(n&1) существенное замечание.
}

@correcеt -1 / 3 / 1 Регистрация: 20.04.2011 Сообщений: 412
	28.03.2016, 09:13 [ТС]	4
	k399et, что-то не очень понятно что выводит ваш элегантный пирмер,ибо при запуске у меня консоль закрывается,system("PAUSE"); не помогает 0

	28.03.2016, 10:00