Создайте треугольник из звезд с помощью только рекурсию
Я должен для записи метода, как который называют printTriangle(5);. Мы должны создать повторяющийся метод и рекурсивный метод (без ЛЮБОГО повторения). Вывод должен быть похожим на это:
*
**
***
****
*****
Этот код работает с повторяющимся, но я не могу адаптировать его, чтобы быть рекурсивным.
public void printTriangle (int count) {
int line = 1;
while(line <= count) {
for(int x = 1; x <= line; x++) {
System.out.print("*");
}
System.out.print("\n");
line++;
}
}
Я должен отметить, что Вы не можете использовать переменные уровня класса или любые внешние методы.
8 ответов
Обратите внимание, что в вашем итеративном подходе у вас есть два счетчика: первый - это ваша линия , линия , а второй - какая позиция на линии, на которой вы находитесь x . Вы можете создать рекурсивную функцию, которая принимает два параметра и использует их как вложенные счетчики, y и x . Если вы уменьшаете x, пока он не достигнет 0, затем уменьшаете y и устанавливаете x = y, пока и x, и y не станут равными 0.
Вы также могли заметить, что каждая последующая строка в треугольнике - это предыдущая строка плюс одна звезда. Если ваша рекурсивная функция возвращает строку звездочек для предыдущей строки, следующая строка всегда будет этой строкой плюс еще одна звезда. Итак, ваш код будет примерно таким:
public String printTriangle (int count) {
if( count <= 0 ) return "";
String p = printTriangle(count - 1);
p = p + "*";
System.out.println(p);
return p;
}
Пример на python (только для прототипирования, но я надеюсь, что идея будет реализована):
#!/usr/bin/env python
def printTriangle(n):
if n > 1:
printTriangle(n - 1)
# now that we reached 1, we can start printing out the stars
# as we climb out the stack ...
print '*' * n
if __name__ == '__main__':
printTriangle(5)
Результат выглядит следующим образом:
$ python 2717111.py
*
**
***
****
*****
Я думаю, это должно сработать ... непроверено в моей голове.
public void printTriangle(int count)
{
if (count == 0) return;
printTriangle(count - 1);
for (int x = 1; x <= count; x++) {
System.out.print("*");
}
System.out.print("\n");
}
Это можно сделать так:
Метод получает количество звезд в качестве параметра. Назовем это n.
Затем он:
рекурсивно вызывает себя с n-1.
выводит строку с n звездами.
Не предпринимайте никаких действий, если n == 0.
Итак, вам нужно создать небольшой блок. Какая информация нужна этому блоку? Максимум. Но рекурсия должна знать, на какой строке она находится ... вы получаете конструктор вроде:
public void printTriangle (int current, int max)
Теперь используйте это, чтобы собрать остальную часть рекурсии вместе:
public void printTriangle (int current, int max)
{
if (current <= max)
{
// Draw the line of stars...
for (int x=0; x<current; x++)
{
System.out.print("*")
}
// add a newline
System.out.print("\n");
// Do it again for the next line, but make it 1-bigger
printTriangle(current + 1, max);
}
}
Теперь все, что вам нужно сделать, это инициировать it:
printTriangle(1, 5);
Вы можете преобразовать цикл в рекурсивную функцию следующим образом:
void printStars(int count) {
if (count == 0) return;
System.out.print("*");
printStars(count - 1);
}
printStars(5); //Prints 5 stars
Вы должны иметь возможность сделать аналогичную функцию для печати строк.
package playground.tests;
import junit.framework.TestCase;
public class PrintTriangleTest extends TestCase {
public void testPrintTriangle() throws Exception {
assertEquals("*\n**\n***\n****\n*****\n", printTriangleRecursive(5, 0, 0));
}
private String printTriangleRecursive(int count, int line, int character) {
if (line == count)
return "";
if (character > line)
return "\n" + printTriangleRecursive(count, line + 1, 0);
return "*" + printTriangleRecursive(count, line, character + 1);
}
}
Вы также можете сделать это с помощью одной (не такой элегантной) рекурсии, как показано ниже:
public static void printTriangle (int leftInLine, int currLineSize, int leftLinesCount) {
if (leftLinesCount == 0)
return;
if (leftInLine == 0){ //Completed current line?
System.out.println();
printTriangle(currLineSize+1, currLineSize+1, leftLinesCount-1);
}else{
System.out.print("*");
printTriangle(leftInLine-1,currLineSize,leftLinesCount);
}
}
public static void printTriangle(int size){
printTriangle(1, 1, size);
}
Идея состоит в том, что параметры метода представляют собой полный рисунок штат.
Обратите внимание, что размер должен быть больше 0.