Geek Answers Handbook

What should be the best way to solve the recurrence relation for a really large quantity greater than the maximum value of Integer

I want to find the Nth number of the repeat equation

T(n)=T(n-1)+3T(n-2)+3T(n-3)+(n-4),T(1)=T(4)=1,T(2)=T(3)=3

therefore, if you entered 2.5.9 as input, the output should be T(2)=3,T(5)=20,T(9)=695

what I did was create an array of size equal to the maximum value of all input values, and save the solution T (i) in index i. Then look into the array for a specific index. for example, array [3] for T (3), array [5] for T (5), etc.

The code worked fine until the maximum number is greater than the maximum integer value system may contain ie

Integer.MAXValue.

Since the index of the array can only be an integer, then if it is a number n=1855656959555656, then what should be the best way to find a solution T(1855656959555656)? since i obviously cannot create an arraysize=1855656959555656..

I even tried BigInteger out java.Math, but without success. I have to find some other approach. Suggest a few ideas.

thank

+4
source share
6 answers

you do not need to store each T (i), you only need to store 3 values ​​of T (i-1), T (i-2), T (i-3). Going through i, check if the current i should be part of your output if it is immediately output or saved in an "output" arrest.

edit: . iteation .

        for (int k = 0; k < arr.length; ++k) {
            if (count == arr[k])
                T[k] = temp[i];
            else if (arr[k] == 1)
                T[k] = 1;
            else if (arr[k] == 2)
                T[k] = 3;
            else if (arr[k] == 3)
                T[k] = 3;
            else if (arr[k] == 4)
                T[k] = 1;
        }

(max * arr.length), (max). HashMap = requiredPosition (= count) value = position in arr

:

 Map<Long, Integer> map = new HashMap<Long, Integer>();
 for (int i = 0; i < arr.length; i++) {
        map.put(arr[i], i);
    }

if (map.containsKey(count)) {
    T[map.get(count)] = temp[i]
}

1-4 !

+4

. Integer.MAX_VALUE ( - 5 8, JVM). ?. , .

+1

. , . - .

+1

: ( , , /):

public void t(long n) {
  if (n < 5) {
    return (n == 2 || n == 3) ? 3 : 1;
  }
  long i = 5;     // Initialize variables for n == 5;
  long tn_1 = 1;  // T(n-1) = T(4) = 1;
  long tn_2 = 3;  // T(n-2) = T(3) = 3;
  long tn_3 = 1;  // T(n-3) = T(2) = 1;
  long tn_4 = 3;  // T(n-4) = T(1) = 3;
  while (true) {
    long tn = tn_1 + 3*tn_2 + 3*tn_3 + tn_4;
    if (i++ == n) {
      return tn;
    }
    tn_4 = tn_3;
    tn_3 = tn_2;
    tn_2 = tn_1;
    tn_1 = tn;
  }
}

:

, (TreeMap HashMap) Long BigInteger:

Map<Long,Long> t = new TreeMap<Long,Long>()

, , .

, ( ):

public class LongArray {
  static final long BLOCK_SIZE = 0x40000000;
  long[][] storage;

  public LongArray(long size) {
    long blockCount = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    storage = new long[][(int) blockCount];
    for (long i = 0; i < blockCount; i++) {
      if (i == blockCount - 1) {
        storage[i] = new long[(int) size - BLOCK_SIZE * (blockCount - 1)];
      } else {
        storage[i] = new long[(int) BLOCK_SIZE];
      }
    }
  }

  public long get(long index) {
    return storage[(int) (index / BLOCK_SIZE)][(int) (index % BLOCK_SIZE)];
  }

  public void put(long index, long value) {
    storage[(int) (index / BLOCK_SIZE)][(int) (index % BLOCK_SIZE)] = value;
  }
}

t.get(index) t.put(index, value) t[index] ( t - ).

+1
source

Use recursive call:

int T(int n){
    if (n==1 || n==4){
       return 1;
    } else if (n==2 || n==3){
       return 3;
    } else {
       return T(n-1)+3*T(n-2)+3T*(n-3)+T(n-4);
    }
}

Edit: time. Will not work with large numbers

0
source

You can do one thing. Make sure that n is equal to 1855656959555656 at the beginning or its multiplicity. Suppose the value of n is two times from 1855656959555656. Then you can create two arrays and link them together practically. This should solve your problem, but it will require a lot of overhead.

0
source

More articles:


All Articles