题目思路

首先我们假设当前的矩形长为 $x$，宽为 $y$，要分出 $k$ 块，那么不难想到分出的一块的长 $dx$ 最短为$x/k$，宽 $dy$ 最短为 $y/k$，而且每次切的长度一定是 $dx$ 的倍数或 $dy$ 的倍数，于是我们递归搜索能切的每个比例，每次切长或者宽，在分出的两块中取比值的最大值，更新最大值的最小值，返回即可。

代码

Python代码

def dfs(x, y, n):
	x, y = max(x, y), min(x, y)		#规定x为长，y为宽
	if n == 1:	#如果当前只是切成一块，则返回长宽比
		return x/y
	dx, dy = x/n, y/n		#所能切的最小单位
	ans = 1e9		#返回值
	for i in range(1, n//2+1):		#切长有n/2中决策，切成(dx,(n-1)dx)、(2dx,(n-2)dx) ....，切宽一样
        #切下dx*i,y 的矩形，剩余部分为 x-dx*i, y，面积比是i:n-i，所以dfs(dx*i, y, i)是第一块的最后结果，
        #dfs(x-dx*i, y, n-i)是第二块的，二者取max得到最大值，最小化最大值，所以和ans取min
		ans = min(ans, max(dfs(dx*i, y, i), dfs(x-dx*i, y, n-i)))
        #切宽同理
		ans = min(ans, max(dfs(x, dy*i, i), dfs(x, y-dy*i, n-i)))
	return ans
x, y, n = map(int, input().split())
print("%.6lf"%dfs(x,y,n))	#直接输出即可

C++代码

#include <iostream>
using namespace std;

double dfs(double x, double y, int n)
{
    double a = min(x, y);
    double b = max(x, y);
    x = b, y = a;	//规定x为长，y为宽
    if (n == 1)	//如果当前只是切成一块，则返回长宽比
        return x / y;	
    double dx = x / n, dy = y / n;	//所能切的最小单位
    double ans = 1e9;
    for (int i = 1; i <= n / 2; i++) {	//切长有n/2中决策，切成(dx,(n-1)dx)、(2dx,(n-2)dx) ....，切宽一样
        //切下dx*i,y 的矩形，剩余部分为 x-dx*i, y，面积比是i:n-i，所以dfs(dx*i, y, i)是第一块的最后结果，
        //dfs(x-dx*i, y, n-i)是第二块的，二者取max得到最大值，最小化最大值，所以和ans取min
        ans = min(ans, max(dfs(dx * i, y, i), dfs(x - dx * i, y, n - i)));
        ans = min(ans, max(dfs(x, dy * i, i), dfs(x, y - dy * i, n - i)));//切宽同理
    }
    return ans;
}
int main()
{
    double x,y;
    int n;
    cin>>x>>y>>n;
    printf("%.6lf\n", dfs(x,y,n));
    return 0;
}

Java代码

import java.util.Scanner;

class Main {
    public static double dfs(double x, double y, int n) {
        double a = Math.min(x, y);
        double b = Math.max(x, y);
        x = b;	//规定x为长，y为宽
        y = a;
        if (n == 1)	//如果当前只是切成一块，则返回长宽比
            return x / y;
        double dx = x / n, dy = y / n;	//所能切的最小单位
        double ans = 1e9;
        for (int i = 1; i <= n / 2; i++) {	//切长有n/2中决策，切成(dx,(n-1)dx)、(2dx,(n-2)dx) ....，切宽一样
            //切下dx*i,y 的矩形，剩余部分为 x-dx*i, y，面积比是i:n-i，所以dfs(dx*i, y, i)是第一块的最后结果，
        	//dfs(x-dx*i, y, n-i)是第二块的，二者取max得到最大值，最小化最大值，所以和ans取min
            ans = Math.min(ans, Math.max(dfs(dx * i, y, i), dfs(x - dx * i, y, n - i)));
            ans = Math.min(ans, Math.max(dfs(x, dy * i, i), dfs(x, y - dy * i, n - i)));//切宽同理
        }
        return ans;
    }

    public static void main(String[] args) {
        double x, y;
        int n;
        Scanner scanner = new Scanner(System.in);
        x = scanner.nextDouble();
        y = scanner.nextDouble();
        n = scanner.nextInt();
        System.out.printf("%.6f", dfs(x, y, n));
    }
}

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
	input += data;
	return;
});
process.stdin.on('end', () => {
    function roundFun(value, n) {	//保留n位小数的函数
      return Math.round(value*Math.pow(10,n))/Math.pow(10,n);
    }
    function dfs(x,y,n)
    {
        let a = Math.min(x, y);
        let b = Math.max(x, y);
        x = b, y = a;	//规定x为长，y为宽
        if (n == 1)	//如果当前只是切成一块，则返回长宽比
            return x / y;
        let dx = x / n, dy = y / n;	//所能切的最小单位
        let ans = 1e9;
        for (let i = 1; i <= parseInt(n / 2); i++) {	//切长有n/2中决策，切成(dx,(n-1)dx)、(2dx,(n-2)dx) ....，切宽一样
            //切下dx*i,y 的矩形，剩余部分为 x-dx*i, y，面积比是i:n-i，所以dfs(dx*i, y, i)是第一块的最后结果，
        	//dfs(x-dx*i, y, n-i)是第二块的，二者取max得到最大值，最小化最大值，所以和ans取min
             ans = Math.min(ans, Math.max(dfs(dx * i, y, i), dfs(x - dx * i, y, n - i)));
             ans = Math.min(ans, Math.max(dfs(x, dy * i, i), dfs(x, y - dy * i, n - i)));//切宽同理
        }
        return ans;
    }
    input=input.split('\n');
    let x=Number(input[0].split(' ')[0]);
    let y=Number(input[0].split(' ')[1]);
    let n=Number(input[0].split(' ')[2]);
    console.log(roundFun(dfs(x,y,n),6));
})

题目内容

小红买了一个长为 $a$ ,宽为 $b$的大饼,一共有 $n$ 个人来一起吃这张大饼，要求每个人必须获得相同面积的大饼。现在小红被要求每一切只能平行于一块大饼的一边(任意一边)，并且必须把这块大饼切成两块。那么我们要切成 $n$ 块饼的话，小红必须切 $n-1$ 次。

小红患有重度强迫症，他一定要求 $n$ 块大饼的长边与短边的比值的最大值最小。你能帮小红计算出这个比值吗

输入描述

一行三个整数 $a$ , $b$ , $n$ , 分别表示大饼的长，宽以及人数

输出描述

一个浮点数，保留 $6$ 位小数，表示切分后大饼的长边与短边的比值

样例

输入：

1 2 3

输出：

1.500000