Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
#1

Реализовать код данной функции, но через рекурсию - C++

21.04.2013, 22:06. Просмотров 1066. Ответов 31
Метки нет (Все метки)

Добрый вечер. Прошу помочь реализовать функцию Mult с помощью рекурсии. Там формируется матрица произведений. Вот сделть, чтобы она формировалась рекурсивно. Эта функция находится в function.cpp. Заранее большое спасибо за ответы и советы)

Собственно вот задание Имеется 2*N чисел. Известно, что их можно разбить на пары таким образом, что произведения чисел в пара:х равны. Сделать разбиение, если числа:
а) натуральные;
б) целые.
Решение: В качестве входных данных будет массив, записанный в файл. Количество элементов в нем должно быть четное, для того, чтобы можно было сформировать пары чисел. Задача будет решена путем построения двумерной матрицы (n*n), где n – количество элементов в исходном массиве. Каждый элемент такой матрицы будет содержать произведение элементов из исходного массива, рассматриваемого относительно индексов в двумерном массиве. Например, в двумерной матрице элемент с индексами (1,2) будет являться произведением элементов из исходного массива с индексами (1) и (2) соответственно. Если исходный массив можно разбить на пары чисел с одинаковым произведением между ними, то любая строка двумерной матрицы будет содержать одно повторяющееся значение. Цель программы – построить двумерную матрицу и отыскать такое произведение. Отыскав это произведение, будет несложно построить пары чисел с одинаковым произведением. Замечание: исходные пары будут содержать числа в единственном экземпляре, или другими словами, повторяющиеся пары не будут учитываться. Это будет продемонстрировано в контрольном примере ниже.
Программа написана таким образом, что она учитывает сразу 2 варианта задания, когда числа натуральные и когда числа целые.
Я не прикрепил файл с входными данными и заголовочный файл.
файл Function.cpp
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <math.h>
#include "Function.h"
using namespace std;
 
int StrToInt(char * str) 
{
    int len=strlen(str);
    int temp=0;
    //переменная для формирования числа
    int i;
    if (str[0]!='-')
        i=0;
    //условие на проверку какое число: отрицательное или положительное
    else
        i=1;
    for (i;i<len;i++)
    {
        switch (str[i])
        {
            case '1':
                temp+=1*pow(10.0,double(len-i-1));
                break;
            case '2':
                temp+=2*pow(10.0,double(len-i-1));
                break;
            case '3':
                temp+=3*pow(10.0,double(len-i-1));
                break;
            case '4':
                temp+=4*pow(10.0,double(len-i-1));
                break;
            case '5':
                temp+=5*pow(10.0,double(len-i-1));
                break;
            case '6':
                temp+=6*pow(10.0,double(len-i-1));
                break;
            case '7':
                temp+=7*pow(10.0,double(len-i-1));
                break;
            case '8':
                temp+=8*pow(10.0,double(len-i-1));
                break;
            case '9':
                temp+=9*pow(10.0,double(len-i-1));
                break;
            case '0':
                temp+=0*pow(10.0,double(len-i-1));
                break;
        }
    }
    if (str[0]=='-')
        temp=-temp;
    //если число отрицательное
    return temp;
}
 
void AnalizingStr(char * str, int * arr1, int n)
{
    int i=0;
    char * tmpstr = new char [10];
    //временная строка для каждого числа из файла
    int j=0;
    int k=0;
    while (str[i]!='\0')
    {
        if (str[i]!=' ')
        {
            tmpstr[j]=str[i];
            j++;
            if ((str[i+1]==' ') || (str[i+1]=='\0'))
            {
                tmpstr[j]='\0';
                j=0;
                arr1[k]=StrToInt(tmpstr);
                //вызов функции перевода числа из символьного типа в числовой
                k++;
            }
        }
        i++;
    }
    delete [] tmpstr;
}
 
int Mult(int * arr1, int * arr2, int n, int & m)
{
    m=0;
    //количество элементов в массиве, содержащий пары
    int ** indexes = new int * [n];
    //двумерная матрица для построения произведений различных пар
    int i,j,k;
    //счетчики
    for (i=0;i<n;i++)
        indexes[i]=new int [n];
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            indexes[i][j]=arr1[i]*arr1[j];
            //формирование произведений чисел в каждой паре
        }
    }
    int mult;
    //переменная для поиска одинакового произведения в парах
    int count;
    //переменная, отвечающая за количество встретившихся одинаковых произведений в строках двумерной матирцы
    int globalflag=0;
    //флаг, отвечающий за то, были ли построены все пары из входного массива
    int flag;
    //локальный флаг для исключения повторений в результирующих парах
    for (i=1;i<n;i++)
    {
        count=0;
        mult=indexes[0][i];
        for (j=1;j<n;j++)
        {
            for (k=0;k<n;k++)
            {
                if ((j!=k) && (indexes[j][k]==mult))
                {
                    //если в строке найдено искомое произведение
                    count++;
                    break;
                }
            }
        }
        if (count==(n-1))
        {
            //если искомое произведение есть во всех строках двумерной матрицы
            globalflag=1;
            for (j=0;j<n;j++)
            {
                for (k=0;k<n;k++)
                {
                    //циклы по двумерной матрице для формирования пар
                    if (indexes[j][k]==mult)
                    {
                        //если в строке найдено искомое произведение
                        flag=0;
                        for (int h=0;h<m;h+=2)
                        {
                            //проверка на иключение повторения пар
                            if ((arr2[h]==arr1[j]) && (arr2[h+1]==arr1[k]))
                                flag=1;
                            if ((arr2[h]==arr1[k]) && (arr2[h+1]==arr1[j]))
                                flag=1;
                        }
                        if (flag==0)
                        {
                            //если пара чисел не встречается в уже составленных парах, то записываем ее в результирующий массив
                            arr2[m++]=arr1[j];
                            arr2[m++]=arr1[k];
                        }
                    }
                }
            }
        }
    }
    for (i=0;i<n;i++)
        delete [] indexes[i];
    delete [] indexes;
    if (globalflag==1)
        return 1;   //если пары были построены
    else
        return 0;   //если пары не были построены
}
файл main.cpp
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include "Function.h"
using namespace std;
 
void main(int argc, char* argv[])
{
setlocale(0, "rus");
    char * filestr = new char [100];
    //строка для ввода адреса к файлу
    cout<<"Укажите адрес к файлу (с расширением):"<<endl;
    cin>>filestr;
    FILE * fr = fopen(filestr,"r");
 
    /*FILE * fr;
    if(argc!=2)//проверка аргументов на наличе
    {
        cout<<"Ошибка!"<<endl;
        exit(-1);
    }
    fr=fopen(argv[1],"r");//открываем файл на чтение, r-значит на чтение
    if(!fr) exit(-1);//проверка есть ли файл*/
 
    if (!fr)
    {
        //если файл не был найден
        delete [] filestr;
        cout<<"Файл не найден. Программа закрывается!"<<endl;
        system("pause");
        return;
    }
    delete [] filestr;
    cout<<endl;
    int count=0;
    //переменная для количества чисел в файле
    int countch=0;
    //переменная для количества символов в файле
    char ch;
    while ((ch=fgetc(fr))!='\n')
    {
        countch++;
        if (ch==' ')
            count++;
    }
    if ((count+1)%2!=0)
    {
        //если количество чисел в файле не четное
        fclose(fr);
        cout<<"Количество чисел в не четное! Пожалуйста исправьте входные данные и перезапустите программу."<<endl;
        return;
    }
    char * str = new char [countch+1];
    int * arr1 = new int [count+1];
    int * arr2 = new int [count+1];
    fseek(fr,0,SEEK_SET);
    //смещаем указатель на файл
    fgets(str,countch+1,fr);
    //считываем первую строку из файла с числами
    AnalizingStr(str,arr1,count+1);
    //вызов функции для анализа и перевода чисел из символьного типа в числовой
    int check;
    //переменная для проверки, построены ли пары чисел
    int m;
    //количество элементов в результирующем массиве, содержащем пары
    check=Mult(arr1,arr2,count+1,m);
    cout<<"Входной массив:"<<endl;
    for (int i=0;i<count+1;i++)
        cout<<arr1[i]<<" ";
    //вывод исходного массива
    cout<<endl;
    if (check==1)
    {
        //вывод пар чисел
        cout<<"Пары:"<<endl;
        for (int i=0;i<m;i+=2)
            cout<<"("<<arr2[i]<<","<<arr2[i+1]<<")"<<endl;
    }
    else
        cout<<"Не удалось сформировать пары"<<endl;
    delete [] str;
    delete [] arr1;
    delete [] arr2;
    fclose(fr);
    getch();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2013, 22:06     Реализовать код данной функции, но через рекурсию
Посмотрите здесь:
Реализовать вывод чисел в диапазоне от 10 до 25 через рекурсию C++
C++ Описание функции через рекурсию
C++ Программу, которая реализует решение задачи, через рекурсию, так и итеративной функции
Реализовать данный код через функцию C++
Реализовать рекурсию C++
C++ Реализовать программу на рекурсию про шахматную доску
Создать динамический массив. ввод,вывод и обработку элементов массива реализовать через функции C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,438
21.04.2013, 22:44     Реализовать код данной функции, но через рекурсию #2
Цитата Сообщение от lj23lj Посмотреть сообщение
произведения чисел в пара:х равны.
Это что значит?
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
21.04.2013, 22:48  [ТС]     Реализовать код данной функции, но через рекурсию #3
kravam, ой, а это опечатка. Надо просто произведения чисел в парах равны..
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,438
21.04.2013, 22:53     Реализовать код данной функции, но через рекурсию #4
Это так что ли:
5, 4
2, 10
1, 20
?
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
21.04.2013, 23:02  [ТС]     Реализовать код данной функции, но через рекурсию #5
kravam, да,да. Именно.
Т.е,если мы возьмем исходные данные, представляющие собой натуральные числа:
4 6 3 2 1 12, то программа сделает так:
(4,3)
(6,2)
(1,12)
Ну или исходные: -4 6 3 -2 1 -12 6 -2, а программа даёт:
(-4,3)
(6,-2)
(1,-12)

Добавлено через 4 минуты
Вот ещё на всякий случай заголовочник сюда отправлю.
C++
1
2
3
4
5
6
7
8
9
10
11
#ifndef _FUNCTION_
#define _FUNCTION_
 
int StrToInt(char * str);
//функция для перевода числа из символьного типа в числовой
void AnalizingStr(char * str, int * arr1, int n);
//функция для выделения чисел из строки в файле
int Mult(int * arr1, int * arr2, int n, int & m);
//функция для формирования пар из исходного массива
 
#endif
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,438
21.04.2013, 23:16     Реализовать код данной функции, но через рекурсию #6
А матрица какая будет?
Щас буду долго тренироваться с ихней таблицей
a -> 16, 24,12,8,4,48,A -> 24,36, 18, 12, 6, 72
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
21.04.2013, 23:20  [ТС]     Реализовать код данной функции, но через рекурсию #7
kravam, не совсем понял вопроса про матрицу?
Мож для тренировки прикрепить файл проекта или исполняемый, чтоб было легче тренироваться? или уже скомпиллилось?
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,438
21.04.2013, 23:26     Реализовать код данной функции, но через рекурсию #8
Такая?
16 | 24 | 12 | 8 | 4 | 48
24 | 36 | 18 | 12 | 6 | 72
12 | 18 | 9 | 6 | 3 |36
8 | 12 | 6 | 4 |2 |24
4 | 6 | 3 | 2 |1 |12
48 | 72 | 36 | 24 |1 |144
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
21.04.2013, 23:34  [ТС]     Реализовать код данной функции, но через рекурсию #9
Мне кажется, что верно, если согласно:
двумерной матрицы (n*n), где n – количество элементов в исходном массиве. Каждый элемент такой матрицы будет содержать произведение элементов из исходного массива, рассматриваемого относительно индексов в двумерном массиве. Например, в двумерной матрице элемент с индексами (1,2) будет являться произведением элементов из исходного массива с индексами (1) и (2) соответственно. Если исходный массив можно разбить на пары чисел с одинаковым произведением между ними, то любая строка двумерной матрицы будет содержать одно повторяющееся значение.

Добавлено через 4 минуты
Кстати, на этом форуме есть решение этой же задаче, но на паскале Даны 2n чисел таких, что их можно разбить на пары таким образом что произведение чисел в парах равны
И алгоритм тоже есть подробнее http://algolist.manual.ru/olimp/sor_sol.php#a10
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,438
21.04.2013, 23:38     Реализовать код данной функции, но через рекурсию #10
Э, не ну его на фиг. На вопрос ответь- такая матрица будет?

++++++++++++++++++++++++++++++++

"Если исходный массив можно разбить на пары чисел с одинаковым произведением между ними, то любая строка двумерной матрицы будет содержать одно повторяющееся значение."

Где тут повторяющиеся значения в ЛЮБОЙ строке? Нету.
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
21.04.2013, 23:42  [ТС]     Реализовать код данной функции, но через рекурсию #11
да, такая матрица)
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,438
21.04.2013, 23:43     Реализовать код данной функции, но через рекурсию #12
Ну вот, матрица такая. А повторяющихся значений нет ни в одной строке, хотя в решении написано:
"Если исходный массив можно разбить на пары чисел с одинаковым произведением между ними, то любая строка двумерной матрицы будет содержать одно повторяющееся значение."
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
21.04.2013, 23:55  [ТС]     Реализовать код данной функции, но через рекурсию #13
Я просто пытался согласно решению массив ваш к матрице привести. видать, не вышло это у меня...
kravam
быдлокодер
1693 / 880 / 44
Регистрация: 04.06.2008
Сообщений: 5,438
22.04.2013, 00:14     Реализовать код данной функции, но через рекурсию #14
Ты где это решение взял-то?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2013, 00:22     Реализовать код данной функции, но через рекурсию
Еще ссылки по теме:
Число из 10-ой в 2-ю ,через рекурсию. C++
Факториал через рекурсию C++
последовательность через рекурсию C++
НОД через рекурсию C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
lj23lj
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 34
22.04.2013, 00:22  [ТС]     Реализовать код данной функции, но через рекурсию #15
Решение нашлось в архиве ресурса одного. Вроде, как расписано вменяемо. Программа работает по алгоритму, расписанному в этом решении. Или в этом есть сомнения?
Yandex
Объявления
22.04.2013, 00:22     Реализовать код данной функции, но через рекурсию
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru