当前位置: 代码迷 >> Eclipse >> 求诸位大神帮帮忙,一道编程题
  详细解决方案

求诸位大神帮帮忙,一道编程题

热度:67   发布时间:2016-04-23 12:49:19.0
求各位大神帮帮忙,一道编程题
把一个正整数分解成3个质数,如果可以 打印该数 和3个质数 不可以就return 错误信息;
求正解……

------解决方案--------------------
for example
Java code
import java.util.*;public class Test {    public static void main(String[] args) throws Throwable {        int n = 1000; //测试1000以内的数据        for (int i=3; i<n; i++) {            findPn(i, 3);        }    }    public static void findPn(int n, int count) throws Exception { //把n分解为count个质数的和        if (n <= 0 || count <= 0 || count > n) { //非法数据的时候,异常退出            throw new Exception("no result");        }        if (count == n) { //n和count相同的时候,n就是count个1相加            System.out.printf("%d=1", n);            for (int i=1; i<count; i++) {                System.out.printf("+%d", 1);            }            System.out.println();            return;        }        int[] num = new int[count-1]; //声明一个count-1个元素的数组,用于保存分解的结果        Arrays.fill(num, 1);//初始化数组每个元素为1        int remain = n; //定义一个变量用于保存分解成count-1个数以后还剩下的值        boolean found = true; //定义一个变量用于判断分解的数是否都是质数        while (num[0] < n - count + 1) { //循环遍历拆分n为count个数的和            found = true;            remain = n;            for (int i=0; i<num.length; i++) { //拆分保存到数组中的元素是否都是质数                found &= isPn(num[i]);                if (! found) break;                remain -= num[i]; //拆分到数组后剩余的数            }            found &= isPn(remain);//判断剩余的数是否都是质数            if (found) { //如果拆分的结果都是质数                System.out.printf("%d=%d", n, num[0]);                for (int i=1; i<num.length; i++) {                    System.out.printf("+%d", num[i]);                }                System.out.printf("+%d\n", remain);                return; //找到一组结果就退出            }                        num[num.length-1]++; //数组元素分配调整,最后一个元素加1            remain = 1; //设定剩余值为1,就是保证必须要有剩余值,否则不能满足count个数之和(因为数组是count-1个)            for (int i=num.length-1, sum=0; i>0; i--, sum=0) {                for (int j=0; j<i; j++) { //求出每个数组元素位置之前的元素的和                    sum += num[j];                }                if (num[i] == n - sum + remain) { //判断数组元素分配是否达到最大                    num[i] = 1; //如果达到最大,则重新分配数组元素为1                    num[i-1]++; //数组元素位置的前一个位置的元素加1                }                remain += num[i]; //调整剩余值            }        }        throw new Exception("no result"); //如果找不到结果就抛出异常    }    public static boolean isPn(int n) { //判断一个数是否是质数        if (n <= 0) return false; //如果小于等于0,不是质数        else if (n < 4) return true; //小于4,也就是1到3都是质数        for (int i=2; i<=(int)(Math.sqrt(n)); i++) { //判断除了1和本身之外是否有因数            if (n%i == 0) return false; //有则不是质数        }        return true;//没有则是质数    }}
  相关解决方案