Перевод с рекурсивного в итерационный метод

@Mr_Foster · Регистрация: 21.09.2013

Студворк — интернет-сервис помощи студентам

Перевод в итерационный метод.
Нужно убрать рекурсию.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void su(int[] m, int[] s, int i, int p, int l, int size, int corsize)   
        {
            for (; i < l; i++)
            {
                if (corsize + m[i] == size)
                {
                    for (int j = 0; j <= p; j++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }
                    Console.WriteLine("{0} = {1};", m[i], size);
                }
                else if (corsize + m[i] < size)
                {
                    s[p + 1] = i;
                    su(m, s, i + 1, p + 1, l, size, corsize + m[i]); // рекурсия
                }
            }
        }

@rattrapper · 28.09.2014, 00:10

Mr_Foster, объясните, что делает метод, а то с такими названиями переменных мозг вывихнуть можно

@Mr_Foster · 28.09.2014, 00:38 **[ТС]**

Ввести массив с n целых чисел. Определить, можно ли с этих чисел выбрать такие, что их сумма равняется числу s. Если вариант существует, результат вывести на экран.
Например, входные данные: 7, 5, 4, 4, 1; s=10; 10 = 5+4+1.

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace alroritm33
{
    class Class1
    {
        static void su(int[] m, int[] s, int i, int p, int l, int size, int corsize)    
        {
            for (; i < l; i++)
            {
                if (corsize + m[i] == size)
                {
                    for (int j = 0; j <= p; j++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }
                    Console.WriteLine("{0} = {1};", m[i], size);
                }
                else if (corsize + m[i] < size)
                {
                    s[p + 1] = i;
                    su(m, s, i + 1, p + 1, l, size, corsize + m[i]); // рекурсия
                }
            }
        }
        static void summ(int[] m, int l, int size)
        {
            int[] s = new int[l];
            su(m, s, 0, -1, l, size, 0);
        }
        static void Main(string[] args)
        {
            int l = 5;                  // размер массива
            int[] m = new int[l];       // массив
            int a;                      // условное число
            Console.Write("Введите условное число: ");
            a = int.Parse(Console.ReadLine());
            for (int j = 0; j < l; j++)
            {
                Console.Write("Введите элемент массива: ");
                m[j] = int.Parse(Console.ReadLine());
            }
            summ(m, l, a);
        }
    }
}

@rRczZZ · 28.09.2014, 01:11

Mr_Foster, а нужно именно переделать? есть вот такой интересный вариант, для небольших n

Кликните здесь для просмотра всего текста

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
static string Test(int Sum, int[] Array)
{
    // Выходная строка
    string[] @out = new string[Array.Length];
    int out_len;
    
    for (uint i = 0; i < 1 << Array.Length; i++ )
    {
        out_len = 0;
 
        // сумма для данного варианта
        int s = 0;
 
        for (uint j = 0, l = i; l != 0; j++, l >>= 1 )
        {
            if (l % 2 == 1)
            {
                s += Array[j];
                @out[out_len++] = Array[j].ToString();
            }
        }
 
        if (s == Sum)
        {
            return out_len == 0 ?
                "0 = " + Sum :
                String.Join(" + ", @out, 0, out_len) + " = " + Sum;
        }
    }
 
    return "не существует";
}
 
static void Main()
{
    int[] a = { 1, 2, 3, 4, 5 };
 
    Console.WriteLine(Test(2 + 4, a));
    Console.ReadLine();
}

@Mr_Foster · 28.09.2014, 11:23 **[ТС]**

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

@Mr_Foster · 29.09.2014, 16:10 **[ТС]**

Проблема не решена

@tarasalk · 29.09.2014, 16:19

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
static void su(int[] m, int[] s, int i, int p, int l, int size, int corsize)   
     {
         bool flag=true;
         while(flag)
         {
            for (; i < l; i++)
            {
                if (corsize + m[i] == size)
                {
                    for (int j = 0; j <= p; j++)
                    {
                        Console.Write("{0} + ", m[s[j]]);
                    }
                    Console.WriteLine("{0} = {1};", m[i], size);
                }
                else if (corsize + m[i] < size)
                {
                    s[p + 1] = i;
                }
                else
                {
                 flag=false;
                 }
            }
         }
        }

Код не проврял, на глаз чисто. Думаю суть вы поняли.

@Mr_Foster · 01.10.2014, 21:03 **[ТС]**

Может я чего-то не понимаю, но у меня не выходит.
Получилось один раз просчитать, но не все возможные варианты как с помощью рекурсии.

@rattrapper · 01.10.2014, 21:42

Mr_Foster, я бы рекурсивный так делал:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static bool CanCombineSumRec(int sum, List<int> numbers)
{
    for (int i = 0; i < numbers.Count; i++)
    {
        if (numbers[i] == sum) return true;
        if (numbers[i] > sum) continue;
        var temp = numbers[i];
        numbers.RemoveAt(i);
        if (CanCombineSumRec(sum - temp, numbers))
            return true;
        numbers.Insert(i, temp);
    }
    return false;
}

На счет итерационного нужно подумать

Добавлено через 1 минуту
блин, так не будет результата

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@rattrapper foo(); 886 / 587 / 222 Регистрация: 03.07.2013 Сообщений: 1,549 Записей в блоге: 2
	28.09.2014, 00:10
	Mr_Foster, объясните, что делает метод, а то с такими названиями переменных мозг вывихнуть можно 0

@Mr_Foster 0 / 0 / 1 Регистрация: 21.09.2013 Сообщений: 13
	28.09.2014, 11:23 [ТС]
	rRczZZ, да переделать, потому что мне потом нужно сравнить два метода(рекурсивным способом и итерационным) на быстродействие, по времени засечь. 0

@Mr_Foster 0 / 0 / 1 Регистрация: 21.09.2013 Сообщений: 13
	29.09.2014, 16:10 [ТС]
	Проблема не решена 0

@Mr_Foster 0 / 0 / 1 Регистрация: 21.09.2013 Сообщений: 13
	01.10.2014, 21:03 [ТС]
	Может я чего-то не понимаю, но у меня не выходит. Получилось один раз просчитать, но не все возможные варианты как с помощью рекурсии. 0