Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
1

Как вернуть исходные значения?

18.11.2010, 15:48. Просмотров 1115. Ответов 17
Метки нет (Все метки)

Вот вопрос, который мучает меня не первый день:

пусть мы имеем массив натуральных чисел от 1 до N, в котором числа не повторяются, скажем, для N=4 это будет: a[1]=2 a[2]=3 a[3]=4 a[4]=1
Зная этот массив, мы легко можем найти элементы массива a[a[i]], в котором вместо индексов - значения элементов нашего массива:
a[a[1]]=3 a[a[2]]=4 a[a[3]]=1 a[a[4]]=2.

А как решить обратную задача? Известен массив a[a[i]], найти элементы массива a[i]?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2010, 15:48
Ответы с готовыми решениями:

Вернуть исходные значения формы по кнопке "Отмена"
Здравствуйте! Я новичок в JavaScript, возник такой вопрос: есть кнопка "редактировать". при...

Как вернуть исходные данные в MaskedTextBox при нажатии Esc
При запуске формы в текстбоксах уже есть изначальные данные. Мне нужно что бы при изменении этих...

Вернуть исходные данные
Здравствуйте, помогите пожалуйста как вычислить и вернуть исходные данные по стоимости (при нажатии...

как вернуть (вывести) 4 значения
подскажите пожалуйста, есть код, но что-то немогу разобраться с функцией, у меня она должна...

Как вернуть 2 значения из функции?
Добрый день. У меня такой вопрос - как в этой проге можно вернуть 2 значения из функции? #include...

17
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
18.11.2010, 16:26 2
А никак. Однозначного решения нет.
Простейший пример:
Последовательность (1, 2).
a[a[1]] = 1;
a[a[2]] = 2;

Последовательность (2, 1).
a[a[1]] = 1;
a[a[2]] = 2;

Добавлено через 4 минуты
Восстановить перестановку P, если известен только её квадрат P^2, однозначно нельзя.

Добавлено через 2 минуты
Или может вам любую такую перестановку найти надо? Или все такие перестановки?
0
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
18.11.2010, 16:45  [ТС] 3
Достаточно одного любого решения. А оно должно быть, раз задача существует. В ней написано "найти любой исходный массив или сообщить, что его не существует"

Насчет "никак" я с вами не соглашусь. Я нашел решение с помощью полного перебора перестановок, но оно меня не удовлетворяет, т.к. сам алгоритм формирования перестановок достаточно громоздок и выдает решение только для малых N, а мне нужен алгоритм работающий хотя бы для N=100

Возможно, надо применять рекурсивную процедуру, но я в этом плохо ориентируюсь
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
18.11.2010, 17:05 4
Если вдруг это задача с какого-нибудь онлайн-контестера, дайте ссылку, пожалуйста.

Добавлено через 6 минут
Переписка
[16:51:40] Хохол: Дана перестановка P. Найти любую перестановку Q такую, что Q^2 = P. Или сказать что таких нет.
[16:51:59] Caesar: опять жесть какая-то
[16:52:48] Хохол: N <= 100
[16:52:53] Alexei: а это задача
[16:52:57] Alexei: я думал калядин))
[16:53:03] Хохол: упаси боже
[16:53:09] Alexei: ты контрольную писал у него?
[16:53:14] Хохол: я видел его ровно один раз в жизни
[16:53:16] Хохол: не писал
[16:53:20] Caesar: а как вообще перестановки в квадрат возводить?
[16:53:25] Pavel: )))))
[16:53:29] Caesar: это типа переставить так вот
[16:53:37] Pavel: дважды применить
[16:53:39] Alexei: зря не писал - там халява, и досрочный экзамен халява
[16:53:46] Хохол: ну типа P^2[i] = P[P[i]]
[16:53:50] Caesar: понял
[16:54:35] Pavel: решил вроде )
[16:54:50] Pavel: за квадрат
[16:54:52] Constantine Drozdov: о_О
[16:54:59] Constantine Drozdov: разбиваем на циклы
[16:55:24] Хохол: а если их нет?
[16:55:32] Alexei: если нет это Е
[16:55:35] Pavel: они всегда есть
[16:55:38] Хохол: шутка
[16:55:40] Constantine Drozdov: очевидно, что четный цикл при возведении в квадрат разбивается на 2 по четным и нечетным места
[16:56:24] Alexei: четным и нечетным местам
это не понял
[16:56:39] Constantine Drozdov: (1234) => (13)(24)
(123) => (132)
(12345)=>(13524)
[16:57:00] Alexei: теперь понял
[16:57:09] Constantine Drozdov: осталось обратить операцию
[16:57:18] Pavel: да
[16:57:29] Хохол: Во блин. Я не понимаю эти скобочки. Я не хожу к калядину.
[16:57:31] Pavel: чётные циклы равных длин собираем парочками и склеиваем
[16:57:36] Alexei: зря
[16:57:49] Alexei: калядин классный препод
[16:57:51] Constantine Drozdov: (1234) перестановка 1 в 2, 2 в 3, 3 в 4, 4 в 1
[16:57:51] Pavel: нечетные циклы звёздочкой перебираем
[16:58:01] Constantine Drozdov: там фейл
[16:58:13] Constantine Drozdov: надо на группы разбивать
[16:58:29] Pavel: ты за O(n) хочешь?
[16:58:37] Alexei: чётные циклы равных длин собираем парочками и склеиваем
почему это плохо?
[16:58:40] Pavel: все быстро отключили смайлики )
[16:58:54] Pavel: да, почему?
[16:58:56] Constantine Drozdov: а у тебя левый ноу-солюшн не будет?
[16:59:09] Pavel: не будет, а сфигали?
[16:59:16] Pavel: а
[16:59:21] Pavel: ну все циклы равных длин
[16:59:22] Pavel: не токо чётные
[16:59:29] Pavel: это когда склеиваем, четные )
[16:59:31] Constantine Drozdov: т.е. если четных циклов данной длины нечетное число всегда ноу-солюшн?
[16:59:40] Pavel: щас подумаю
[16:59:44] Constantine Drozdov: любой нечетный цикл обратим, да
[17:00:15] Constantine Drozdov: а ну да, очевидно, что четные циклы получаются из четных
[17:00:26] Constantine Drozdov: и только из них
[17:00:30] Constantine Drozdov: по 2
[17:00:37] Constantine Drozdov: значит их всегда четное число одинаковой длины)
[17:00:46] Constantine Drozdov: вот вам и О(n)
[17:01:03] Pavel: да
[17:01:11] Pavel: O(n) есть
[17:01:17] Pavel: теперь за O(1) давайте ))

К сожалению, ухожу, и пока на человеческий язык перевести это не могу.
0
18.11.2010, 17:05
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
18.11.2010, 21:21  [ТС] 5
Я проанализировал. Не убедило.
Это задача вряд ли опубликована.
0
Mr.X
Эксперт С++
3190 / 1717 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
19.11.2010, 14:27 6
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
//////////////////////////////////////////////////////////////////////////////////////
//пусть мы имеем массив натуральных чисел от 1 до N, в котором числа не повторяются, 
//скажем, для N=4 это будет: a[1]=2 a[2]=3 a[3]=4 a[4]=1
//Зная этот массив, мы легко можем найти элементы массива a[a[i]], 
//в котором вместо индексов - значения элементов нашего массива:
//a[a[1]]=3 a[a[2]]=4 a[a[3]]=1 a[a[4]]=2.
//
//А как решить обратную задача? Известен массив a[a[i]], найти элементы массива a[i]?
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef size_t                    T_elem;
typedef std::set<T_elem>          T_elem_set;
typedef std::vector<T_elem*>      T_substitutions;
//////////////////////////////////////////////////////////////////////////////////////
void  get_substitutions_sqrt
    (
        size_t                 substitution_size,        
        const T_elem* const    substitution,
        const T_elem_set&      elem_set,        
        T_elem* const          substitution_sqrt,
        T_substitutions&       substitutions_sqrt_res
    )
{
    T_elem*  first_zero_it
        = std::find(substitution_sqrt, substitution_sqrt + substitution_size, 0);   
    
    int  first_zero_pos = std::distance(substitution_sqrt, first_zero_it); 
 
    for(T_elem_set::const_iterator  set_elem_it = elem_set.begin();
        set_elem_it != elem_set.end(); ++set_elem_it)
    {
        T_elem*     substitution_sqrt_cur = new  T_elem[substitution_size];
        std::copy(substitution_sqrt, substitution_sqrt + substitution_size, 
                  substitution_sqrt_cur);
 
        T_elem_set  elem_set_cur(elem_set);        
 
        T_elem      pos_cur   = first_zero_pos;
        T_elem      elem_cur  = *set_elem_it;
        
        for(;;)
        {
            if(substitution_sqrt_cur[pos_cur] == 0)
            {
                if(elem_set_cur.find(elem_cur) == elem_set_cur.end())
                {
                    break;
                }
                substitution_sqrt_cur[pos_cur] = elem_cur;
                elem_set_cur.erase(elem_cur);
                if(elem_set_cur.empty())
                {                    
                    substitutions_sqrt_res.push_back(substitution_sqrt_cur);
                    break;
                }
                elem_cur  = substitution[pos_cur];            
                pos_cur   = substitution_sqrt_cur[pos_cur] - 1;            
            }
            else if(substitution_sqrt_cur[pos_cur] == elem_cur)
            {
                if(elem_set_cur.empty())
                {                    
                    substitutions_sqrt_res.push_back(substitution_sqrt_cur);
                }
                else
                {
                    get_substitutions_sqrt
                        (
                            substitution_size,
                            substitution,
                            elem_set_cur,
                            substitution_sqrt_cur,
                            substitutions_sqrt_res
                        );                               
                }
                break;                
            }
            else break;
        }//for(;;)     
    }//for(T_elem_set::const_iterator  set_elem_it = elem_set.begin();    
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int  n;
    do
    {
        std::cout << "Введите количество элементов в подстановке > 0: ";
        std::cin >> n;
    }while(n <= 0);
 
    std::cout << "Введите подстановку из "
              << n
              << " элементов:"
              << std::endl;
 
    T_elem_set  elem_set;    
    T_elem*     substitution = new  T_elem[n];
    bool        elem_is_good;
 
    int  subst_ind_cur = 0;
    do
    {
        std::cout << "#"
                  << elem_set.size() + 1
                  << ": ";
 
        T_elem  cur_elem;
        std::cin >> cur_elem;
        elem_is_good = (1 <= cur_elem && cur_elem <= static_cast<T_elem>(n))
                       && elem_set.find(cur_elem) == elem_set.end();
 
        if(elem_is_good)
        {
            elem_set.insert(cur_elem);            
            substitution[subst_ind_cur++] = cur_elem;
        }
    }while(!elem_is_good
           || elem_set.size() < static_cast<T_elem>(n));   
 
    T_elem*  substitution_sqrt = new  T_elem[n];   
        
    std::fill_n(substitution_sqrt, n, 0);
    T_substitutions  substitutions_sqrt;
 
    get_substitutions_sqrt
        (
            n,
            substitution, 
            elem_set,
            substitution_sqrt,
            substitutions_sqrt
        );
 
    if(substitutions_sqrt.empty())
    {
        std::cout << "Не существует подстановки, квадратом которой являлась бы заданная.";
    }
    else
    {
        std::cout << "Подстановки, квадратом которых является заданная:"
                  << std::endl;
        int counter = 0;        
        
        for(T_substitutions::iterator  
            sqrt_substitution_it = substitutions_sqrt.begin();
            sqrt_substitution_it != substitutions_sqrt.end(); ++sqrt_substitution_it)
        
        {
            std::cout << "#"
                      << ++counter
                      << ":\t";
            
            std::copy(*sqrt_substitution_it, *sqrt_substitution_it + n,
                      std::ostream_iterator<T_elem>(std::cout, " "));          
 
            std::cout << std::endl;
        }       
    }
    std::cout << std::endl;
}
2
Tronix
157 / 104 / 6
Регистрация: 22.08.2010
Сообщений: 215
19.11.2010, 15:35 7
Mr.X,

Дело в том, что меня тоже заинтересовала данная задача. Спасибо за готовый солюшен, но не могли бы вы на словах немного пояснить принцип работы вашей программы? Си++ для меня увы, как брейнфак примерно. Ну или поставить пару-тройку комментариев в программе. Спасибо.
0
Mr.X
Эксперт С++
3190 / 1717 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
19.11.2010, 16:35 8
Цитата Сообщение от Tronix Посмотреть сообщение
Mr.X,

Дело в том, что меня тоже заинтересовала данная задача. Спасибо за готовый солюшен, но не могли бы вы на словах немного пояснить принцип работы вашей программы? Си++ для меня увы, как брейнфак примерно. Ну или поставить пару-тройку комментариев в программе. Спасибо.
Да все элементарно. Запишем один под другим три вектора:

1 2 3
X X X
3 1 2

где средний вектор – искомая подстановка, а нижний - ее заданный квадрат. Подставим в первую позицию искомой подстановки цифру 1. Так как под ней стоит 3, то это означает, что в искомой подстановке единица отображается в тройку, следовательно и под единицей верхнего вектора должна стоять тройка, а там единица, что неверно.
Подставим на первую позицию двойку, что означает, что в искомой подстановке присутствует отображение 2 -> 3, следовательно под двойкой верхнего вектора нужно подписать 3, а так как под этой тройкой единица, то в искомой подстановке присутствует отображение 3 -> 1, следовательно под тройкой верхнего вектора нужно подписать 1. Одно из решений найдено.
Как только очередной цикл в искомой подстановке заканчивается, очередное значение приходится искать перебором.
1
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
19.11.2010, 17:16  [ТС] 9
Mr.X, жаль, что вместо С я изучал паскаль, но, зная принцип алгоритма я постараюсь разобраться
0
Black Fregat
2978 / 1594 / 452
Регистрация: 31.05.2009
Сообщений: 5,682
19.11.2010, 20:13 10
Никакого перебора не требуется. Можно построить конструктивный алгоритм. Единственное решение вообще строится легко, перебор всех вариантов - чуть сложнее

Добавлено через 4 минуты
Mr.X, нескромный вопрос - если уж Вы постарались написать полностью кошерный код С++, то почему first_zero_pos имеет тип int ?

Добавлено через 2 минуты
Раз уж в коммерческой ветке граждане не захотели купить этот алгоритм за 500 рублей, опубликую - не пропадать же добру.. Но только позже - сейчас меня из здания выгонять будут, а мне еще остальные дела закруглять
0
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
19.11.2010, 20:46  [ТС] 11
Блестящее решение этой задачи предложил Сергей (ms@samaralan.ru ). Всё гениально просто, ни перебора, ни рекурсии, никаких функций и процедур, кроме pred и succ. За что ему мой огромный респект и уважуха.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
19.11.2010, 21:21 12
Расскажите решение, пожалуйста.
0
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
19.11.2010, 23:37  [ТС] 13
Mr.X, это всё, конечно хорошо, но решение предложенное Сергеем уместилось в один цикл for, то есть задача решена за 1 проход по массиву, просто найден красивый алгоритм присвоения величинам значений номеров
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
19.11.2010, 23:49 14
Цитата Сообщение от кот Бегемот Посмотреть сообщение
решение уместилось в один цикл for, то есть задача решена за 1 проход по массиву
Не верю
0
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
20.11.2010, 02:14  [ТС] 15
А это дело хозяйское.
Как с сусликом:
Видишь суслика? - Нет.
И я не вижу. А он есть.
0
silent_1991
Эксперт С++
5020 / 3080 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
20.11.2010, 05:13 16
А почему бы не выложить код, чтобы, так сказать, все убедились. Нам всё-таки делиться завещали.
0
кот Бегемот
Платежеспособный зверь
8588 / 4001 / 1568
Регистрация: 28.10.2009
Сообщений: 10,475
20.11.2010, 09:35  [ТС] 17
Не вопрос, просто в реальности задача была сложнее, чем заявлена в теме, и решение сделано для более сложной задачи. А задача, описанная здесь, решена внутри этой, более сложной задачи.

Итак, общая задача:
Массив А состоит из неповторяющихся чисел от 1 до N
Массив B сформирован из массива А по закону: B[A[A[i]]]=i
По данному массиву В найти массив А

Pascal
1
2
3
4
5
for i := 0 to n - 1 do begin
       k := Src[i];
       k := Src[Pred(k)];
        Dst[Pred(k)] := Succ(i);
     end;
0
unStatiK
Заблокирован
20.11.2010, 14:37 18
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Не вопрос, просто в реальности задача была сложнее, чем заявлена в теме, и решение сделано для более сложной задачи. А задача, описанная здесь, решена внутри этой, более сложной задачи.

Итак, общая задача:
Массив А состоит из неповторяющихся чисел от 1 до N
Массив B сформирован из массива А по закону: B[A[A[i]]]=i
По данному массиву В найти массив А

Pascal
1
2
3
4
5
for i := 0 to n - 1 do begin
       k := Src[i];
       k := Src[Pred(k)];
        Dst[Pred(k)] := Succ(i);
     end;
Это особенность реализаций функций , смысл которых в том что сохранять значения после изменения .
Если нужно вручную проделать такой же алгоритм , то нужно сначало реализовать это сохраниение что уместится не в один цикл . И уж только потом благодаря этим функциям выполнять что требуется .
0
20.11.2010, 14:37
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2010, 14:37

Как вернуть значения из цикла?
Как вернуть значения из цикла? Например существует массив изображений &quot;IM&quot;; public Image...

Массивы. Найти максимальные и минимальные значения. В строках, где находятся искомые значения все значения обратить в ноль и вернуть номер строки
Всем привет! Вот такая задачка: Ввести двумерный массив 5х6. Найти максимальные и минимальные...

Как правильно вернуть значения из метода?
Ребят, есть вот такой вот баян ниже. Для возврата нескольких значений, говорят нужно создавать...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

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