Zadanie z C - najmniejsza wartość wielomianu

0

Mam takie zadanie:

zad.png

Rozwiązałem je tak:

 #include <stdio.h>
#include <math.h>

void pokaz(unsigned int n, double tab[])
{
    unsigned int i = 0;
    for(i=0; i<n; i++)
        printf("tab[%d] = %f\n", i, tab[i]);
    printf("\n");
}

void zad3(double a, double b, double c, double d, int n, int m)
{
    int i, x;
    int rozmiar = (m-n)+1;

    printf("rozmiar = %d\n", rozmiar);

    double *temp = malloc(sizeof(double)*rozmiar);

    x = n;
    for(i=0; i<rozmiar; i++)
    {
        printf("x = %d\n", x);

        double wartosc = a*pow(x,3) + b*pow(x,2) + c*x + d;
        temp[i] = wartosc;
        x ++;
    }

    printf("\n");
    pokaz(rozmiar, temp);
    printf("\n");

    double minwart = temp[0];
    for(i=0; i<rozmiar; i++)
    {
        if(minwart > temp[i])
            minwart = temp[i];
    }
    printf("min = %f\n", minwart);

    free(temp);
    temp = NULL;
}

int main(int argc, char **argv)
{
    zad3(1, 2, 3, 4, 3, 5);

    return 0;
}

Jest to zadanie z podstaw programowania. Czy istnieje jakieś prostsze rozwiązanie? Wydaje mi się, że tak, bo skoro to są podstawy ... Można to jakoś uprościć?

1

Pomijając rozwiązania analityczne, mógłbyś zwiększyć/uzmiennić rozdzielczość sprawdzania. W Twoim przykładzie sprawdzasz tylko trzy punkty: 3, 4 i 5.

Poza tym, nie widzę potrzeby alokowania pamięci na wszystkie wyniki, możesz je sprawdzać na bieżąco.

0

Poprzednie rozwiązanie (chyba) jest błędne. To wydaje się działać dobrze (policzyłem na kartce):

int zad3b(double a, double b, double c, double d, int n, int m)
{
    double wartosc = 0, minel = 0;
    int x = 0, ix = n;

    minel = wartosc = a*pow(n,3) + b*pow(n,2) + c*n + d;

    for(x=n; x<=m; x++)
    {
        wartosc = a*pow(x,3) + b*pow(x,2) + c*x + d;
        if(minel > wartosc)
        {
            ix = x;
            minel = wartosc;
        }
    }
    return ix;
}
 
1

Opcje są tutaj dwie. Jedna ma złożoność O(1) druga O(m-n). Nie napisałeś jakie są zakresy danych więc trudno oceniać która jest tutaj tą poprawną.
Opcja naiwna O(m-n) to oczywiście policzenie wartości funkcji od kolejnych liczb n, n+1, n+2, ... ,m i wybranie minimum.
Opcja szybka wymaga sprawdzenia:

  • krańców przedziałów (funkcja(n), funkcja(m))
  • ekstremów zadanej funkcji które mieszczą się w przedziale. W tym celu musimy sprawdzić gdzie zeruje się pochodna tego wielomianu, tzn gdzie
    3ax^2 +2bx +c = 0. To jest zwykłe równanie kwadratowe więc sprawdzamy sobie klasycznie deltę, sprawdzamy czy jest nieujemna a potem liczymy pierwiastki i wybieramy tylko te które są w przedziale <n,m>. Oczywiście jeden to minium a drugi to maksimum ale sprawdzenie który jest który jest bardziej kosztowne niż policzenie wartości funkcji w obu ;)

edit: oczywiście szukamy liczb całkowitych, więc jak dobrze zauważył @bogdans, musimy sprawdzić dla każdego ekstremum dwie sąsiadujące z nim liczby całkowite, czyli floor(x) i ceil(x).

W takiej sytuacji liczymy wartość funkcji tylko w 4 punktach czyli mamy O(1).
W takiej sytuacji liczymy wartość funkcji tylko w 6 punktach czyli mamy O(1).

0

Ale czy moje (drugie) rozwiązanie jest prawidłowe? O złożoność na razie się nie martwię ;)

0
#include <stdio.h>

int zad3(double a, double b, double c, double d, int n, int m)
  {
   double y,best;
   int retx;
   retx=n;
   best=(((a*n+b)*n+c)*n+d;
   for(++n;n<=m;++n)
      {
       y=(((a*n+b)*n+c)*n+d;
       if(best>y)
         {
          retx=n;
          best=y;
         }
      }
   return ret;
  }
 
int main()
  {
   printf("min=%d\n",zad3(1,2,3,4,3,5));
   return 0;
  }
0

Ok dziękuję wszystkim za pomoc

1 użytkowników online, w tym zalogowanych: 0, gości: 1