如何将这个迭代语句转换为递归语句？

huangapple
go评论88阅读模式
英文:

How can I convert this iterative statement into a recursive statement?

问题

所以我有一个编程项目，需要创建一个程序来确定一个数字是否是一个完美平方数，如果是，就将其写入一个 .txt 文档。使用 for 循环可以很容易有效地实现这一点，然而，作业的说明要求这个程序应该使用递归来实现。以下是我想出来的迭代语句：

  1. double division;
  2. for (int i = 0; i < inputs.size(); i++) {
  3.     division = (Math.sqrt(inputs.get(i)));
  4.     if (division == (int)division) {
  5.         pw.println(inputs.get(i));
  6.     }
  7. }

其中 inputs 是一个由用户输入创建的 ArrayList。这个方法解决了问题，但正如我所说，它需要变成一个递归语句。我知道对于递归，我需要一个基本情况，最终使方法停止调用自身，但我想不出基本情况是什么。另外，我看过几个从迭代转换为递归的例子，但所有这些例子都使用单个 int 变量，在我的情况下，我需要使用 ArrayList 来实现。任何帮助将不胜感激。

英文:

So I have this programming project in which I need to create a program that determines if a number is a perfect square, and if so, write it into a .txt document. This is very easy and effective to do with a for loop, however, the instructions for the assignment say that the program should accomplish this using recursion. This is the iterative statement I came up with:

  1. double division;
  2. 		for (int i = 0; i &lt; inputs.size(); i++) {
  3. 			division = (Math.sqrt(inputs.get(i)));
  4. 			if (division == (int)division) {
  5. 				pw.println(inputs.get(i));
  6. 			     }
  7. 			}

Where inputs is an ArrayList that is created by reading the inputs of the user.
This solves the problem, but like I said, it needs to be a recursive statement. I know that for recursion I need a base case that will eventually make the method stop calling itself, but I can't figure out what the base case would be. Also, I've seen several examples of converting from iteration to recursion, but all of these examples use a single int variable, and in my case I need to do it with an ArrayList.
Any help would be greatly appreciated

答案1

得分: 1

对于递归函数，您可以使用二分搜索算法：

  1. int checkPerfectSquare(long N,
  2.                               long start,
  3.                               long last)
  4. {
  5.     // 找到起始和结束位置的中间值
  6.     long mid = (start + last) / 2;
  8.     if (start > last)
  9.     {
  10.         return -1;
  11.     }
  13.     // 检查是否找到了平方根为 N 的完全平方数
  14.     if (mid * mid == N)
  15.     {
  16.         return (int)mid;
  17.     }
  19.     // 如果平方(mid)大于 N，则表示只有小于 mid 的值可能是 N 的平方根
  20.     else if (mid * mid > N)
  21.     {
  22.         return checkPerfectSquare(N, start,
  23.                                   mid - 1);
  24.     }
  26.     // 如果平方(mid)小于 N，则表示只有大于 mid 的值可能是 N 的平方根
  27.     else
  28.     {
  29.         return checkPerfectSquare(N, mid + 1,
  30.                                   last);
  31.     }
  32. }
英文:

For recursive function, you can use bynary search algorithm:

  1.  int checkPerfectSquare(long N,  
  2.                               long start, 
  3.                               long last) 
  4. { 
  5.     // Find the mid value 
  6.     // from start and last 
  7.     long mid = (start + last) / 2; 
  8.   
  9.     if (start &gt; last) 
  10.     { 
  11.         return -1; 
  12.     } 
  13.   
  14.     // Check if we got the number which 
  15.     // is square root of the perfect 
  16.     // square number N 
  17.     if (mid * mid == N) 
  18.     { 
  19.         return (int)mid; 
  20.     } 
  21.   
  22.     // If the square(mid) is greater than N 
  23.     // it means only lower values then mid 
  24.     // will be possibly the square root of N 
  25.     else if (mid * mid &gt; N) 
  26.     { 
  27.         return checkPerfectSquare(N, start,  
  28.                                   mid - 1); 
  29.     } 
  30.   
  31.     // If the square(mid) is less than N 
  32.     // it means only higher values then mid 
  33.     // will be possibly the square root of N 
  34.     else 
  35.     { 
  36.         return checkPerfectSquare(N, mid + 1,  
  37.                                   last); 
  38.     } 
  39. }

答案2

得分: 1

你可以利用一个完全平方数是奇数整数的和这一事实。例如：

1+3 = 4 = 2^2

1+3+5 = 9 = 3^2

1+3+5+7 = 16 = 4^2，依此类推

  1. public static void main(String[] args) {
  2.     for (int i = 1; i < 1000; i++) {
  3.         if (isSquare(i)) System.out.println(i);
  4.     }
  5. }
  7. public static boolean isSquare(int n) {
  8.     if (n==0 || n==1) return true;
  9.     return isSquare(n,1,1);
  10. }
  12. private static boolean isSquare(int n, int sum, int odd) {
  13.     if (n==sum) return true;
  14.     if (n < sum) return false;
  15.     odd += 2;
  16.     sum += odd;
  17.     return isSquare(n, sum, odd);
  18. }

输出结果：

  1. 1
  2. 4
  3. 9
  4. 16
  5. 25
  6. 36
  7. 49
  8. 64
  9. 81
  10. 100
  11. 121
  12. 144
  13. 169
  14. 196
  15. 225
  16. 256
  17. 289
  18. 324
  19. 361
  20. 400
  21. 441
  22. 484
  23. 529
  24. 576
  25. 625
  26. 676
  27. 729
  28. 784
  29. 841
  30. 900
  31. 961
英文:

You could use the fact that a square number is the sum of the odd integers. E.g.

1+3 = 4 = 2^2

1+3+5 = 9 = 3^2

1+3+5+7 = 16 = 4^2, etc

  1. public static void main(String[] args) {
  2.     for (int i = 1; i &lt; 1000; i++) {
  3.       if (isSquare(i)) System.out.println(i);     
  4.     }
  5.   }
  6.   public static boolean isSquare(int n) {
  7.     if (n==0 || n==1) return true;
  8.     return isSquare(n,1,1);
  9.   }
  11.   private static boolean isSquare(int n, int sum, int odd) {
  12.     if (n==sum) return true;
  13.     if (n &lt; sum) return false;
  14.     odd += 2;
  15.     sum += odd;
  16.     return isSquare(n, sum, odd);
  17.   }

output:

  1. 1
  2. 4
  3. 9
  4. 16
  5. 25
  6. 36
  7. 49
  8. 64
  9. 81
  10. 100
  11. 121
  12. 144
  13. 169
  14. 196
  15. 225
  16. 256
  17. 289
  18. 324
  19. 361
  20. 400
  21. 441
  22. 484
  23. 529
  24. 576
  25. 625
  26. 676
  27. 729
  28. 784
  29. 841
  30. 900
  31. 961

答案3

得分: 0

你可以递归地检查任何较小整数的平方是否等于你的输入。

  1. public static boolean isSquare(int n) {
  2.   if (n == 0 || n == 1) return true;
  3.   return isSquare(n, 1);
  4. }
  6. private static boolean isSquare(int n, int i) {
  7.   if (i * i == n) return true;
  8.   if (i * i > n) return false;
  9.   return isSquare(n, i + 1);
  10. }
英文:

You could recursively check if the square of any smaller int is equal to your input.

  1. public static boolean isSquare(int n) {
  2.   if (n==0 || n==1) return true;
  3.   return isSquare(n, 1);
  4. }
  6. private static boolean isSquare(int n, int i) {
  7.   if (i*i == n) return true;
  8.   if (i*i &gt; n) return false;
  9.   return isSquare(n,i+1);
  10. }

huangapple
  • 本文由 发表于 2020年9月6日 09:37:49
  • 转载请务必保留本文链接：https://go.coder-hub.com/63759967.html
  • arraylist
  • iteration
  • java
  • recursion
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定