和为N的连续正整数序列

74 阅读 0 评论 49 点赞

我是靠谱客的博主忧郁黄豆，最近开发中收集的这篇文章主要介绍和为N的连续正整数序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

自然数从1到n之间,有多少个数字含有1

	//定义h(n)=从1到9999.....9999  ( n 个 9)之间含有1的数字的个数
    private int H(int n) {
        //h(1)=f(1)=1
        //h(2)=f(1)+f(2)
        //h(3)=f(1)+f(2)+f(3)
        //h(4)=f(1)+f(2)+f(3)+f(4)
        if(n==1)return 1;
        int rs=0;
        for(int i=1;i<=n;i++) {
            rs+=F(i);
        }
        return rs;
    }
    //定义f(n)为n位数中含有1的数字的个数
    public int F(int n) {
        //f(1)=1
        //f(2)=10^1+8h(1)
        //f(3)=10^2+8h(2)
        //f(4)=10^3+8h(3)
        if(n==1)return 1;
        return (int) (Math.pow(10, n-1)+8*H(n-1));
    }
    //自然数从1到n之间,有多少个数字含有1
    public int sum1(int n) {
        if(n<=0)return 0;
        if(n<=9)return 1;
        String str = String.valueOf(n);
        int len = str.length();
        int rs=H(len-1);
        char[] ch=str.toCharArray();
        //最高位数字在[1-9]
        int first=ch[0]-'0';
        if(first>1) {
            rs+=Math.pow(10, len-1);
            //最高位数字在[3-9]
            if(first>=3) {
                rs+=(first-2)*H(len-1);
            }
            rs+=sum1(Integer.valueOf(str.substring(1,len)));
        }else {
            rs+=Integer.valueOf(str.substring(1,len))+1;
        }
        return rs;
    }

输入一个整数N，求从1到N这N个整数的十进制表示中‘1’出现的次数

	public int count1(int n) {
        if(n<=0) {
            return 0;
        }else if(n<=9) {
            return 1;
        }
        String str = String.valueOf(n);
        char[] ch=str.toCharArray();
        //最高位中1的个数
        int numFirstDigit = 0;
        //最高位数字在[1-9]
        int first = ch[0]-'0';
        if(first>1) {
            //最高位数字>1
            numFirstDigit=(int) Math.pow(10, ch.length-1);
        }else {
            //最高位数字==1
            numFirstDigit = Integer.valueOf(str.substring(1,str.length()))+1;
        }
        //如21345，除最高位外，0-20000中1的个数
        int numOtherDigits = (int) (first*(ch.length-1)*Math.pow(10,ch.length-2));
        int numRecursive = count1(Integer.valueOf(str.substring(1,str.length())));
        return numFirstDigit+numOtherDigits+numRecursive;
    }

输入一个正整数N，求所有和为N的连续正整数序列

连续的正整数表示至少有两个数字。

public void sumAll(int n) {
        ArrayList<HashMap<Integer, Integer>> rs = new ArrayList<HashMap<Integer,Integer>>();
        int left = 1;
        int right = 2;
        int sum = (left+right)*(right-left+1)/2;
        while(left<right) {            
            if(sum<n) {
                right++;
            }else if (sum==n) {
                HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(2);
                map.put(1, left);
                map.put(2, right);
                rs.add(map);
                left++;
            }else {
                left++;
            }
            sum = (left+right)*(right-left+1)/2;
        }
        System.out.println(right);
        Tool.out(rs);
}