Pascal三角形整数溢出：在第30行需要查找值时。

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

Pascal Triangle Integer Overflow when values need to be find at row 30

问题

这是整数溢出问题，但我无法理解如何仅使用整数解决它，而不使用长整数。我想知道在溢出发生时如何测试或形成方程，而不转向更高的数据类型。

目标：尝试找到帕斯卡三角形中第i个索引的值；

rowIndex 可以最大为33。

  1. class Solution {
  2.     public List<Integer> getRow(int rowIndex) {
  3.         
  4.         List<Integer> pt = new ArrayList<>();
  5.         
  6.         int prev = 1;
  7.         int curr = 1;
  8.         int n = rowIndex + 1;
  9.         pt.add(prev);
  10.         
  11.         for (int i = 1; i <= rowIndex; i++) {    
  12.             
  13.             curr = prev * (n - i) / i;
  14.             
  15.             pt.add(curr);
  16.             
  17.             prev = curr;
  18.         }
  19.         return pt;
  20.     }
  21. }
英文:

This is Integer overflow problem but i am not able to wrap my head around it for using only Integer for solution [not using long ].
I want to know how can we test or form equation when overflow happens without moving to higher datatype?

Aim : try to find pascal triangle values at i index ;

rowIndex can be max 33.

Code:

  1. class Solution {
  2.     public List&lt;Integer&gt; getRow(int rowIndex) {
  3.         
  4.         List&lt;Integer&gt; pt = new ArrayList&lt;&gt;();
  5.         
  6.         int prev=1;
  7.         int curr=1;
  8.         int n=rowIndex+1;
  9.         pt.add(prev);
  10.         
  11.         for (int i=1; i &lt;= rowIndex; i++) {    
  12.             
  13.             curr = prev * (n-i)/i;
  14.             
  15.             pt.add(curr);
  16.             
  17.             prev=curr;
  18.         }
  19.         return pt;
  20.         
  21.     }

答案1

得分: 1

你可以通过使用long而不是int来防止溢出。

  1. public List<Integer> getRow(int rowIndex) {
  2.     
  3.     List<Integer> pt = new ArrayList<>();
  4.     
  5.     int prev = 1;
  6.     int curr = 1;
  7.     int n = rowIndex + 1;
  8.     pt.add(prev);
  9.     
  10.     for (int i = 1; i <= rowIndex; i++) {    
  11.         
  12.         curr = (int) ((long) prev * (n - i) / i);
  13.         
  14.         pt.add(curr);
  15.         
  16.         prev = curr;
  17.     }
  18.     return pt;
  19. }

但是，可以在不使用long的情况下解决这个问题。prev * (n - i) 部分可能会溢出，但这个乘积应该能被i整除。您可以通过在乘法之前进行除法来避免溢出。如果提前计算(n - i)和i的最大公约数 (GCD)，则可以按以下方式重写。

  1. int gcd = gcd(n - i, i);
  2. curr = (prev / (i / gcd)) * ((n - i) / gcd);

GCD可以通过以下方法获得。

  1. static int gcd(int m, int n) {
  2.     while (n > 0) {
  3.         int r = m % n;
  4.         m = n;
  5.         n = r;
  6.     }
  7.     return m;
  8. }

在之前：

  1. [1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, -131213633, -123012780, -101304642, -73164463, -46209134, -25415023, -12102391, -4950978, -1722079, -502273, -120545, -23181, -3434, -367, -25, 0]

之后：

  1. [1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, 155117520, 145422675, 119759850, 86493225, 54627300, 30045015, 14307150, 5852925, 2035800, 593775, 142506, 27405, 4060, 435, 30, 1]
英文:

You can prevent overflow by using long instead of int.

  1. public List&lt;Integer&gt; getRow(int rowIndex) {
  2.     
  3.     List&lt;Integer&gt; pt = new ArrayList&lt;&gt;();
  4.     
  5.     int prev=1;
  6.     int curr=1;
  7.     int n=rowIndex+1;
  8.     pt.add(prev);
  9.     
  10.     for (int i=1; i &lt;= rowIndex; i++) {    
  11.         
  12.         curr = (int) ((long) prev * (n-i)/i);
  13.         
  14.         pt.add(curr);
  15.         
  16.         prev=curr;
  17.     }
  18.     return pt;
  19.     
  20. }

But the problem can be solved without using long.
The prev * (n-i) part may overflow, but this product should be divisible by i. You can avoid the overflow by dividing before the multiplication. If you calculate GCD of (n-i) and i in advance, you can rewrite as follows.

  1.         int gcd = gcd(n - i, i);
  2.         curr = (prev / (i / gcd)) * ((n - i) / gcd);

GCD can be obtained by the following method.

  1. static int gcd(int m, int n) {
  2.     while (n &gt; 0) {
  3.         int r = m % n;
  4.         m = n;
  5.         n = r;
  6.     }
  7.     return m;
  8. }

before:

  1. [1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, -131213633, -123012780, -101304642, -73164463, -46209134, -25415023, -12102391, -4950978, -1722079, -502273, -120545, -23181, -3434, -367, -25, 0]

after:

  1. [1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, 155117520, 145422675, 119759850, 86493225, 54627300, 30045015, 14307150, 5852925, 2035800, 593775, 142506, 27405, 4060, 435, 30, 1]

huangapple
  • 本文由 发表于 2020年8月12日 17:51:16
  • 转载请务必保留本文链接：https://go.coder-hub.com/63374037.html
  • integer-overflow
  • java
匿名

发表评论

匿名网友

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

确定