X  
登录

还没有账号?立即注册

忘记密码?
登陆
X  
注册

已经有账号?马上登陆

获取验证码
重新获取(60s)
立即注册
统计
  • 建站日期:2021-03-10
  • 文章总数:683 篇
  • 评论总数:697 条
  • 分类总数:10 个
  • 最后更新:11月26日
文章 精密算法

JAVA 蓝桥杯 国赛 第五届 B组 试题 D: 排列序数

程序员阿鑫
首页 精密算法 正文


JAVA蓝桥杯国赛第五届B组试题D:排列序数
-程序员阿鑫-带你一起秃头!
-第1
张图片

题目描述

如果用a b c d这4个字母组成一个串,有4!=24种,如果把它们排个序,每个串都对应一个序号:
  abcd  0
  abdc  1
  acbd  2
  acdb  3
  adbc  4
  adcb  5
  bacd  6
  badc  7
  bcad  8
  bcda  9
  bdac  10
  bdca  11
  cabd  12
  cadb  13
  cbad  14
  cbda  15
  cdab  16
  cdba  17
  ...

    现在有不多于10个两两不同的小写字母,给出它们组成的串,你能求出该串在所有排列中的序号吗?

【输入格式】
一行,一个串。

【输出格式】
一行,一个整数,表示该串在其字母所有排列生成的串中的序号。注意:最小的序号是0。

例如:
输入:
bdca

程序应该输出:
11

再例如:
输入:
cedab

程序应该输出:
70


资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意:主类的名字必须是:Main,否则按无效代码处理。

答案:

// 这道题用到了  康拓展开   ,如果了解康拓展开,这道题也就没什么难度了
import java.util.Scanner;

public class Main {
    static int[] a; // a[0]:0的阶乘、a[1]:1的阶乘……

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int len = str.length();
        a = new int[len];
        for (int i = 0; i < len; i++) {
            a[i] = f(i);
        }

        int ans = fun(str);
        System.out.println(ans);
        sc.close();
    }

    // 求阶乘
    public static int f(int n) {
        if (n == 0)
            return 1;

        int sum = 1;
        for (int i = 1; i <= n; i++)
            sum *= i;
        return sum;
    }

    // 求序号
    public static int fun(String str) {
        int len = str.length();
        int n = 0;

        for (int i = 0; i < len; i++) {
            int tem = 0;
            char ch1 = str.charAt(i);
            for (int j = i + 1; j < len; j++) {
                char ch2 = str.charAt(j);
                if (ch2 < ch1)
                    tem++;
            }
            n += a[len - 1 - i] * tem;
        }

        return n;
    }
}

以上是《JAVA 蓝桥杯 国赛 第五届 B组 试题 D: 排列序数》的全部内容,

感谢您对程序员阿鑫博客的支持!

版权说明
文章采用: 《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权。
版权声明:未标注转载均为本站原创,转载时请以链接形式注明文章出处。如有侵权、不妥之处,请联系站长删除。敬请谅解!

-- 展开阅读全文 --
这篇文章最后更新于2020-12-9,已超过 1 年没有更新,如果文章内容或图片资源失效,请留言反馈,我们会及时处理,谢谢!
宝塔怎么找回密码,忘记密码怎么找回?
« 上一篇
JAVA 蓝桥杯 国赛 第五届 B组 试题 C: 格子放鸡蛋
下一篇 »
为了防止灌水评论,登录后即可评论!
注册登录

HI ! 请登录
注册会员,享受下载全站资源特权。
登陆 注册
社交账号登录

IP地址

热门文章

1
抖音无限礼物模拟小工具分享
2
QQ假红包引流QQ群教程及代码
4
卡QQ永久大会员方法

最新文章

标签