ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Рекурсия - вопрос как лучше из двух вариантов
7 сообщений из 7, страница 1 из 1
Рекурсия - вопрос как лучше из двух вариантов
    #38195503
Фотография sergei123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sergei123
Участник
Здравствуйте
Данная рекурсивная функция возвращает стринговый список ходов (верх и низ) некой маленькой программы. Знаю список тупо не нужен, но такая задача.

Первый вариант, в каждой рекурсии возвращается текущий ход + список следующих ходов.
Второй вариант, в каждой рекурсии возвращается список следующих ходов, а последняя рекурсия возвращает все ходы.
У какого из двух вариантов меньше траты ресурс?

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
public List<String> listUpDown(String steps) {

		.
		.
		.

		List<String> stringList = new ArrayList<String>();
		
		String add = null;
				
		if(isRight)
			add = "U"; // Up
				
		else if(isLeft)
			add = "D"; // Down
				
		if(add != null) {
			stringList.add(add);
			stringList.addAll(listUpDown(steps + add));
		}
		
		return stringList; 
		
	 }


Код: java
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.
public List<String> listUpDown(String steps) {

		.
		.
		.

		List<String> list = new ArrayList<String>();
		
		String add = null;
				
		if(isRight)
			add = "U"; // Up
				
		else if(isLeft)
			add = "D"; // Down

		else
			list.addAll(Arrays.asList(path.split("(?!^)"))); 
				
		if(add != null)
			list.addAll(listUpDown(steps + add));
		
		return list; 
		
	 }
...
Рейтинг: 0 / 0
22.03.2013, 20:13:07
| Ответить | Цитировать | Написать  
Рекурсия - вопрос как лучше из двух вариантов
    #38195603
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А что isRight не исключает isLeft?
...
Рейтинг: 0 / 0
22.03.2013, 22:26:59
| Ответить | Цитировать | Написать  
Рекурсия - вопрос как лучше из двух вариантов
    #38195623
DoSOfRedRiver
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DoSOfRedRiver
Участник
sergei123,

Наверняка второй, т.к. в нём меньше операций на ступень выходит.
...
Рейтинг: 0 / 0
22.03.2013, 23:22:28
| Ответить | Цитировать | Написать  
Рекурсия - вопрос как лучше из двух вариантов
    #38195671
Фотография sergei123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sergei123
Участник
mayton,

Ну да, если сразу после add = "U"; всунуть:
Код: java
1.
2.
3.
stringList.add(add);
stringList.addAll(listUpDown(steps + add));
return stringList;


и соответственно в isLeft также.
Да и с названиями попутал, isUp и isDown должно быть)))
...
Рейтинг: 0 / 0
23.03.2013, 00:53:59
| Ответить | Цитировать | Написать  
Рекурсия - вопрос как лучше из двух вариантов
    #38195679
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
sergei123, давай полный исходник. Иначе мы запутаемся.
...
Рейтинг: 0 / 0
23.03.2013, 00:59:40
| Ответить | Цитировать | Написать  
Рекурсия - вопрос как лучше из двух вариантов
    #38195690
Фотография sergei123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sergei123
Участник
mayton, пожалуйста:

Код: java
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.
public static List<String> listUpDown(String steps, int[] array, int index) {
		/*
		 *	for example:
		 *	listUpDown({1,3,4,1,3,4,2,5,0}, 0, ""); // return {"R","R","R","L","R","R"}
		 *	listUpDown({2,1,2,3,0}, 0, ""); // return {}
		 */
		
		List<String> stringList = new ArrayList<String>();
		
		Boolean isArray = gameArray.length > 0;
		
		if(isArray) {
			
			int upIndex	= index + array[index],
			    downIndex	= index - array[index];
			
			Boolean isMore	= path.length() < array.length - 1,
				isUp	= upIndex < array.length && upIndex != index,
				isDown	= downIndex > 0 && downIndex != index;
				/*isEnd	= index == array.length -1; если второй вариант то разкомментировать*/
			
			if(isMore) {
				
				String add = null;
				
				if(isUp) {
					add = "U";
					index = upIndex;
				}
				
				else if(isDown) {
					add = "D";
					index = downIndex;
				}
				
				/* если второй вариант то разкомментировать
				else if(isEnd)
					stringList.addAll(Arrays.asList(path.split("(?!^)"))); 
				*/
				
				if(add != null) {
					stringList.add(add); // если второй вариант то закомментировать
					stringList.addAll(listUpDown(steps + add, array, index));
				}
				
			}
			
		}
		
		return stringList; 
		
	 }
...
Рейтинг: 0 / 0
23.03.2013, 01:17:57
| Ответить | Цитировать | Написать  
Рекурсия - вопрос как лучше из двух вариантов
    #38195693
Фотография sergei123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sergei123
Участник
Код: java
1.
2.
3.
for example:
listUpDown("", {1,3,4,1,3,4,2,5,0}, 0); // return {"R","R","R","L","R","R"}
listUpDown("", {2,1,2,3,0}, 0); // return {}
...
Рейтинг: 0 / 0
23.03.2013, 01:22:08
| Ответить | Цитировать | Написать  
7 сообщений из 7, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Рекурсия - вопрос как лучше из двух вариантов
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=38195679&tid=2129720]:
 0ms
get settings:
 21ms
get forum list:
 23ms
check forum access:
 5ms
check topic access:
 5ms
track hit:
 55ms
get topic data:
 19ms
get forum data:
 4ms
get page messages:
 78ms
get tp. blocked users:
 3ms
others: 363ms
total:  576ms
созд. / загр.: 576ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]