Coding a recursive function for highest possible input

Question

Challenge

You are given the following function:- enter image description here which is the same as:-

enter image description here

with the base cases q(r, b, L) = 1 whenever r ≤ L, q(r, 0, L) = 0, if r > L and q(r, 0, L) = 1, if r ≤ L.

Your task is to code a program that takes r as input, and outputs the value of q(r, r - L, L) for all L taking integer values from 1 to (r-1), where r is any nonnegative integer.

Example 1

Input

Enter the value of r: 2

Output

q(2,1,1) = 0.3333333333

Example 2

Input

Enter the value of r: 3

Output

q(3,2,1) = 0.1

q(3,1,2) = 0.5

Winning criterion

The code that can correctly output q(r, r-L, L) for all L taking integer values from 1 to (r-1), for the highest value of r, in less than 300 seconds. In case of a tie, the code with lesser runtime will be considered. As this is a runtime-based challenge, I shall test all submissions on my machine.

Your sum/product notations both use the letter k as their variable. I think this is technically valid, but it might be easier to read if you used two different letters. — stokastic
– stokastic, Commented Dec 7, 2014 at 19:03
Which of the two base cases takes priority when r < L and b = 0? And what value of b will be used in the winning criterion? — Peter Taylor
– Peter Taylor, Commented Dec 7, 2014 at 23:21
@PeterTaylor let me guess: are you working on a closed-form? — Soham Chowdhury
– Soham Chowdhury, Commented Dec 8, 2014 at 7:42
q(r, r-1, 1) == 2(r!)^2/(2r)! (oeis.org/A001700) and r(r, 1, r-1) == (r-1)/(r+1) (trivial). Haven't checked the others yet. — kennytm
– kennytm, Commented Dec 8, 2014 at 17:23
In the interests of clarity, q(r,r-1,1) is the reciprocal of A001700. — Peter Taylor
– Peter Taylor, Commented Dec 10, 2014 at 10:12

Peter Taylor · Accepted Answer · 2014-12-10 00:08:37Z

Java

I've applied some algebraic transformation and dynamic programming.

public class CodeGolf42234 {
    public static void main(String[] args) {
        int r = Integer.parseInt(args[0]);
        for (int L = 1; L < r; L++) System.out.println(qDouble5(r, r-L, L));
    }

    private static double qDouble5(int _r, int _b, int L) {
        double[][] q = new double[_r+1][_b+1];
        for (int r = 0; r <= L; r++) {
            for (int b = 0; b < q[r].length; b++) q[r][b] = 1;
        }
        for (int r = L + 1; r < q.length; r++) {
            for (int b = 1 + (r - L - 1)/L; b < q[r].length; b++) {
                double sum = 0, m = 1;
                for (int k = 0; k <= L; k++) {
                    sum += m * q[r-k][b-1];
                    m = m * (r - k) / (r + b - 1 - k);
                }
                q[r][b] = sum * b / (r + b);
            }
        }
        return q[_r][_b];
    }
}

Thank you for the submission. On my system (Windows, Netbeans IDE), the highest value of r that can be evaluated using this code, in under 300 seconds (297 seconds) is 731. Good job, Peter! :) — Train Heartnet
– Train Heartnet, Commented Dec 10, 2014 at 10:36

Community · Accepted Answer · 2020-06-17 09:04:33Z

Java

Here's a recursive solution. Just like you wanted. You can always uncomment the output and display it if you want.

import java.util.ArrayList;
import java.util.Scanner;


public class HeaderFinder
{
static ArrayList<Double> answers = new ArrayList<Double>();
public static void main(String[]args)
{
    Scanner scanner = new Scanner(System.in);
    int r = scanner.nextInt();
    for(int b=r-1; b!=0; b--)
        for(int L=r-1; L!=0; L--)
            answers.add(formulate(r,b,L));

//  int i=-1;
//      for(int b=r-1; b!=0; b--)
//          for(int L=r-1; L!=0; L--)
//              System.out.println("q("+r+", "+b+", "+L+") = "+answers.get(++i));

}

public static double formulate(double r, double b, double L)
{
    if(b==0)
        if(r>L)
            return 0.0;
        else
            return 1;
    if(r<=L)
        return 1;
    double partone = (b/(r+b));
    double result = 0.0;
    for(int k=1; k<=L; k++)
    {
        result+=summation(r, b, k) * (b/(r+b-k)) * formulate(r-k, b-1, L);
    }
    return (partone * formulate(r, b-1, L)) + result;
}

public static double summation(double r, double b, int k)
{
    double rb = r+b;
    double mul=r/rb;
    for(int i=1; i<k; i++)
    {
        mul*=(r-i)/(rb-i);
    }
    return mul;
}
}

Stack Exchange Network

Coding a recursive function for highest possible input

2 Answers 2

Java

Java

Your Answer

Hot Network Questions

Coding a recursive function for highest possible input

2 Answers 2

Java

Java

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions