首页 > 试题广场 >

飞机最低可俯冲高度

[编程题]飞机最低可俯冲高度
  • 热度指数:301 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
近日,埃航空难的新闻牵动了无数人的心。据悉,空难很可能是由于波音737MAX飞机的失速保护系统错误触发所致。在飞机进行高空飞行时,驾驶辅助系统如果检测到飞机失速,无法维持足够的飞行升力,会压低机头进行俯冲,以重新获得速度,进而获取足够的飞行升力,维持飞行高度。但是在飞机进行低空飞行时,触发俯冲机制极有可能在飞机还未获得足够飞行速度并上升之前已经撞击地面。鉴于半年内的两起事故,波音公司决定在低于一定高度时屏蔽自动俯冲机制,现提供K架飞机用于测试最低可俯冲高度,设定需要测试的海拔范围为1~H(单位米),请问最不理想情况下,至少需要多少次才能求出飞机的最低可俯冲高度?

输入描述:
输入为整数K, H,用空格分隔

K代表用于测试的飞机数量,H代表需要测试的高度范围为1~H米(包含H)


输出描述:
输出整数N,代表最坏情况下需要测试的次数
示例1

输入

1 1000

输出

1000

说明

只有一架飞机用来测试的情况下,从最高高度1000米,逐次减1m进行测试,直到飞机坠毁。
示例2

输入

15 1000

输出

10

说明

飞机数量足够多,每次均使用二分法进行测试

备注:
1-H为低空飞行高度范围,所有大于H的高度都不属于低空飞行,不会在俯冲过程中撞击地面,不需要进行测试。

如果飞机俯冲测试过程中撞击地面坠毁,可以推断本次测试高度低于飞机实际最低可俯冲高度,可测试飞机数量减1。

如果飞机俯冲测试过程中撞击地面前顺利拉升,可以推断本次测试高度高于或等于飞机最低可俯冲高度,本次试验所用飞机可继续用来测试。

tips:
测试飞机中使用无人驾驶远程操控,无需担心飞行员安全。
无需考虑物理学上的合理性。
#include <bits/stdc++.h>
usingnamespacestd;
intmain(){
    intK,N;
    cin>>K>>N;
    vector<int> dp(K + 1, 0);
    intm;
    for(m = 0; dp[K] < N; m++)
            for(intk = K; k > 0; --k)
                dp[k] += dp[k - 1] + 1;
    cout<<m<<endl;
    return0;
}
发表于 2019-06-12 15:17:04 回复(1)

问题等价于:k个鸡蛋,h层楼,最少用多少次能找到哪一层楼摔下去鸡蛋会碎。

先来看简单的场景:

  • k = 1
    首先,如果k=1,很简单,最坏情况下最少要尝试h次。即,最高能探索的层数=最少探索次数。
  • k = 2
    再看k=2即只有两个鸡蛋的场景。
    设最少尝试次数为x,那么x+(x-1)+...+2+1=(x+1)*x/2为最高能探索的层数。
    具体解释为:
    第一次将鸡蛋在第x层放下,如果摔碎了,另一个鸡蛋从第1层开始尝试到第x-1层,一共尝试x次;如果没摔碎,继续将这个鸡蛋从第x+(x-1)层放下,如果摔碎,从第x+1层尝试到第x+(x-1)-1层,即一共x次尝试;如果没摔碎,继续将这个鸡蛋从第x+(x-1)+(x-2)层放下,....

那么当k>2的情况呢?

用动态规划方法求解,假设用j个鸡蛋做i次尝试最高能探索到第dp[i][j]层。当dp[i][j]>h时的i即为所求。

初始状态
dp[i][1] = i:用1个鸡蛋,有i次尝试机会,就能到第i层(因为每次都是往上尝试1层)。
dp[1][j] = 1:有j个鸡蛋,只给1次尝试机会,那么最多只能尝试到第1层。这里注意了,因为只有1次尝试机会,你有再多个鸡蛋也没用。

dp[i][j]:
现在初始状态确定了,来看看dp[i][j]怎么确定,也就是有j个鸡蛋做i次尝试,最高能探索到第几层?

假设我们知道有j-1个鸡蛋做i-1次尝试最高能到几层,那现在多了1个鸡蛋,可以多做1次尝试,那最高能到多少层呢?这第i个鸡蛋只能再做1次尝试,因此,只能在dp[i-1][j-1]+1层尝试。

  1. 如果这次尝试鸡蛋碎了,我们就找到在第dp[i-1][j-1]+1层鸡蛋会碎啦;
  2. 如果这次尝试鸡蛋没碎,那么还能再对j个鸡蛋做i-1次尝试,因此,还能再高dp[i-1][j]层。

因此,dp[i][j] = dp[i-1][j-1] + 1 + dp[i-1][j]

于是,可以写出动态规划的代码:

k, h = [int(x) for x in input().split()]
dp = [1]*(k+1)
cnt = 1
while dp[k] < h:
    cnt += 1
    dp_i_1 = dp[:]
    dp[1] = cnt
    for j in range(2,k+1):
        dp[j] = dp_i_1[j-1] + dp_i_1[j] + 1
print(cnt)

优化一下,变成:

k, h = [int(x) for x in input().split()]
dp = [0] * (k+1)
cnt = 0
while dp[k] < h:
    for i in range(k,0,-1):
        dp[i] += dp[i-1] + 1
    cnt += 1
print(cnt)
编辑于 2019-09-13 17:34:51 回复(0)

使用图+DFS(代码没有优化,可阅读)

package NiuKeWang;

import java.io.File;
import java.io.IOException;
import java.util.*;

/**
 * @Classname XuZhaoGuanLianYongHu
 * @Description TODO
 * @Date 19-5-25 上午10:01
 * @Created by mao<tianmao818@qq.com>
 */
public class XuZhaoGuanLianYongHu {
    public static void main(String[] args)throws IOException {
        Scanner sc=new Scanner(new File("/home/mao/workspace/java/src/NiuKeWang/paypal"));
        //多组输入
        while (sc.hasNext()){
            double d=sc.nextDouble();
            int n=sc.nextInt();

            //建表
            List<List<Double>> table=new ArrayList<>();
            for(int i=0;i<n;i++){
                List<Double> tmp=new ArrayList<>();
                double x=sc.nextDouble();
                double y=sc.nextDouble();
                tmp.add(x);
                tmp.add(y);
                table.add(tmp);
            }

            //建图
            Map<Integer,List<Integer>> map=new HashMap<>();
            for(int i=0;i<n;i++){
                for(int j=i;j<n;j++){
                    double x1=table.get(i).get(0);
                    double y1=table.get(i).get(1);
                    double x2=table.get(j).get(0);
                    double y2=table.get(j).get(1);

                    double dd=distance(x1,y1,x2,y2);

                    if(dd<=d*d){
                        //正向
                        if(map.containsKey(i)){
                            map.get(i).add(j);
                        }else{
                            map.put(i,new ArrayList<>());
                            map.get(i).add(j);
                        }

                        //反向
                        if(map.containsKey(j)){
                            map.get(j).add(i);
                        }else{
                            map.put(j,new ArrayList<>());
                            map.get(j).add(i);
                        }
                    }
                }
            }
            List<List<Integer>> res=find(map);
            List<List<Integer>> ans=new ArrayList<>();
            for(List<Integer> tmp:res){
                tmp.sort(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1-o2;
                    }
                });
                ans.add(tmp);
            }

            ans.sort(new Comparator<List<Integer>>() {
                @Override
                public int compare(List<Integer> o1, List<Integer> o2) {
                    return o1.get(0)-o2.get(0);
                }
            });


            System.out.println(ans);
        }
    }

    public static double distance(double x1,double y1,double x2,double y2){
        return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    }

    public static List<List<Integer>> find(Map<Integer,List<Integer>> map){

        List<List<Integer>> ans=new ArrayList<>();
        int[] visited = new int[map.size()];

        for(int key :map.keySet()){
            List<Integer> tmp=new ArrayList<>();

            if(visited[key]==0){
                tmp.add(key);
                List<Integer> queue=new ArrayList<>();
                for(Integer i:map.get(key)){
                    queue.add(i);
                }
                visited[key]=1;
                while(!queue.isEmpty()){
                    int node=queue.get(0);
                    queue.remove(0);
                    if(visited[node]==0){
                        tmp.add(node);
                        for(Integer i:map.get(node)){
                            queue.add(i);
                        }
                        visited[node]=1;
                    }
                }
            }else {
                continue;
            }
            ans.add(tmp);
        }
        return ans;
    }
}
发表于 2019-05-25 10:31:12 回复(0)