Софтуерно Инженерство
Loading...
Pavletka avatar Pavletka 0 Точки

Closest number, C++

Условието на задачата: Write a program which finds the two closest (by value) integer numbers in an array and prints the absolute difference between them.

Input: 

5

1 105 10 100 3

Output:

2 (The closest numbers are 1 and 3, abs(1,3) = 2)

Това е начинът, по който мисля, че трябва да се реши задачата: 

int n;
    cin>>n;

    int arr[n];
    int i;
    for (i=0; i<n; i++)
    {
        cin>>arr[i];
    }

    int k = INT_MAX;
    int m;

    for(i=0; i<n; i++)
    {
        m = abs(arr[i], arr[i+1]);
        if (m < k)
        {
            k = m;
        }
        cout<<endl;
        cout<<k<<endl;
    }

Може ли някой да ми помогне, защото явно това не е правилният код. Благодаря Ви!

0
C++ Programming
willystyle avatar willystyle 1779 Точки

Имаш предвид, че алгоритъма не ти е верен може би. Така обхождаш масива веднъж и сравняваш разлика между съседни елементи. Това е добро, ако масива е сортиран. Ако не е сортиран, може да направиш още един вложен цикъл и да сравниш m = abs(arr[i], arr[j]); .Но все пак със сортировка мисля, че сложността на алгоритъма е по-малка.

int n;
    cin>>n;

    int arr[n];
    int i;
    for (i=0; i<n; i++)
    {
        cin>>arr[i];
    }

   sort(arr, arr + n);

    int k = INT_MAX;
    int m; int indexMin = 0;

    for(i=0; i<n - 1; i++)
    {
        m = abs(arr[i], arr[i+1]);
        if (m < k)
        {
            k = m; indexMin = i;
        }      
    }

    cout<<endl;
    cout<<k<<endl;

    cout<<arr[indexMin ]<<endl;

     cout<<arr[indexMin + 1]<<endl;

0
29/11/2018 22:47:51
kolioi avatar kolioi 612 Точки

Това няма да работи, ако n=1, т.е. ако имаме само едно число. Точно това е уловката в тази задача. Миналата седмица един колега беше пуснал тема за това. Аз съм го направил така

int min_diff = 0;
if (n > 1)
{
	min_diff = abs(arr[0] - arr[1]);
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			if (abs(arr[i] - arr[j]) < min_diff)
				min_diff = abs(arr[i] - arr[j]);
}
cout << min_diff;

 

1
willystyle avatar willystyle 1779 Точки

Единствено ми прави впечетление, дали i не трябва да върти до n - 1 ? Но това ще спести само 4 операции, със същия резултат от кода :)

0
kolioi avatar kolioi 612 Точки

Твоят код работи добре за повече числа. Обаче при n=1 джадж очаква 0 (това не го пише в условието на задачата), а твоят изход е INT_MAX. Един от тестовете е такъв и затова някои хора вземат само 80/100.

П.П. А моя код е на ниво Софтюни :)

0
30/11/2018 05:23:06
BobyTopalova avatar BobyTopalova 25 Точки

Да, точно така за масив от 1 елемент - разликата е 0 и ако тази проверка липсва Judge дава 80/100 точки

0
Dimitar1236 avatar Dimitar1236 0 Точки

Благодаря ти!

0