Форум программистов, компьютерный форум, киберфорум
avraal
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Нахождение чисел, сумма которых близка к R

Запись от avraal размещена 22.11.2016 в 19:27

Столкнулся с заданием: в одномерном массиве из N найти два различных элемента, сумма которых наиболее близка к числу R, вывести эти элементы. А так же вывести элементы, которые находятся между ними, или вывести сообщение о том, что оба элемента находятся рядом
Приступлю сразу к решению задачи:
Поскольку мне нужно найти сумму двух элементов, которые могут не находится рядом, решил использовать 2 цикла
Через эти циклы я нашёл все сочетания элементов (первый элемент+второй элемент, первый элемент+третий элемент)
Потом делаю проверку на выход второго значения за пределы массива (строки 4-5)
Если модуль разницы суммы i-тего и j-тего элемента с R меньше мой временной переменной _tmp (по-умолчанию равна 0), то в эту переменную модуль разницы я и записываю (строка 8)
Так же есть 2 переменные f(first) и s(second) - они указывают на текущий индекс массива, что позволяет мне запомнить порядковый номер элементов, сумма которых наиболее близка к R
C++
1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 0; i < len; i++)
        for(int j = i+1; j < len; j++)
    {
        if(j >= len)
            break;
        if(abs(mas[i] + mas[j] - R) < _tmp)
        {
            _tmp = abs(mas[i] + mas[j] - R);
            f = i;
            s = j;
        }
    }
Далее нужно найти элементы, которые находятся между f и s элементами массива
Для этого я создаю еще один массив, и переменную отвечающую за его размер
Размер нового массива вычисляется следующим образом: поскольку индекс s всегда будет больше индекса f, то я просто нахожу разницу между ними
C++
1
sec_size = s - f;
Но еще рано заполнять новый массив. Прежде всего нужно определить: стоят ли элементы рядом или между ними есть другие элементы
Вычисляется это, относительно, просто: если каким-то образом разница между s и f равна 0 (ну мало ли) или если разница равна второму индексу (по идее, sec_size = 0 если индекс f равен 0)
C++
1
2
3
4
5
6
7
8
9
10
11
if(sec_size == 0 || sec_size == s)
        cout<<"Оба элемента находятся рядом"<<endl;
    else
    {
        sec_elements = new int[sec_size];
        for(int i = f; i < s; i++)
            sec_elements[i] = mas[i];
        cout<<"Элементы массива, находящиеся на промежутке от "<<f<<" до "<<s<<':';
        for(int i = 0; i < sec_size; i++)
            cout<<sec_elements[i]<<endl;
    }
Дальше, в строке 5 я выделяю память для массива, в строке 6 начинается цикл от f до s, чтобы записать элементы, которые находятся между mas[f] и mas[s](строка 7)
И напоследок, я вывожу эти массивы

Полный код можно найти тут:
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <locale>
#include <cmath>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "rus");
 
    int len, R, _min;
    int f, s;
 
    cout<<"Введите размер массива: ";
    cin>>len;
 
    int *mas = new int[len];
    int *sec_elements;
    int sec_size;
 
    for(int i = 0; i < len; i++)
    {
        cout<<"Введите "<<i+1<<" элемент массива: ";
        cin>>mas[i];
    }
 
    cout<<"Введите R: ";
    cin>>R;
 
    for(int i = 0; i < len; i++)
        for(int j = i+1; j < len; j++)
    {
        if(j >= len)
            break;
        if(abs(mas[i] + mas[j] - R) < _min)
        {
            _min = abs(mas[i] + mas[j] - R);
            f = i;
            s = j;
        }
    }
 
    cout<<"mas["<<f<<"] = "<<mas[f]<<", mas["<<s<<"] = "<<mas[s]<<endl;
 
    sec_size = s - f;
    if(sec_size == 0 || sec_size == s)
        cout<<"Оба элемента находятся рядом"<<endl;
    else
    {
        sec_elements = new int[sec_size];
        for(int i = f; i < s; i++)
            sec_elements[i] = mas[i];
        cout<<"Элементы массива, находящиеся на промежутке от "<<f<<" до "<<s<<':';
        for(int i = 0; i < sec_size; i++)
            cout<<sec_elements[i]<<endl;
    }
 
    return 0;
}


Надеюсь, кому-то моя запись поможет
Спасибо за внимание
Размещено в Без категории
Просмотров 445 Комментарии 1
Всего комментариев 1
Комментарии
  1. Старый комментарий
    сча ступлю))) зачем аж 2 цикла? рассмотрим последовательность натуральных положительных чисел вв максиве $alfa
    $gamma=ориентир;
    while($alfa!=null){
    $beta++;
    if($alfa<$gamma){
    if $gamma-$alfa[$i]>$gamma[$delta]){$delta=$beta;}
    }else{
    ....}

    }
    В случае если нужно вернуть несколько значений то превращаем дельту в массив и производим сравнение по наиболее отдалённому элементу
    Запись от abrdabr размещена 22.11.2016 в 20:38 abrdabr вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.