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 2472 Точки

Имаш предвид, че алгоритъма не ти е верен може би. Така обхождаш масива веднъж и сравняваш разлика между съседни елементи. Това е добро, ако масива е сортиран. Ако не е сортиран, може да направиш още един вложен цикъл и да сравниш 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 641 Точки

Това няма да работи, ако 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 2472 Точки

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

0
kolioi avatar kolioi 641 Точки

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

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

0
30/11/2018 05:23:06
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.