`

是否很久没抽象和逻辑了呢？ DODO它吧(很基础)三

算法SUNJ#CC++ 
阅读更多

17. 字符统计问题。
    编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。

18. 最优服务次序问题。
    设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti， 1<=i<=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小呢?

平均等待时间是n个顾客等待服务时间的总和除以n。
    input： 正整数n，表示n个顾客。 接下来一行输入n个正整数，表示n个顾客需要的服务时间。
    output：最小的平均等待时间

    例如：
    input：
    10
    56 12 1 99 1000 234 33 55 99 812

    output：
    532.00

 

19. 多处最优服务次序问题。
    设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti， 1<=i<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使
平均等待时间达到最小呢?平均等待时间是n个顾客等待服务时间的总和除以n。
    输入：2个正整数n和s,表示有n个顾客且有s处可以提供顾客需要的服务。
          接下来一行中有n个正整数，表式n个顾客需要的服务时间。
    输出：最小的平均等待时间

    例如：
    input：
    10 2
    56 12 1 99 1000 234 33 55 99 812

    output：
    336

20. 最优分解问题。
    设n是一个正整数。现在要求将n分解为若干互不相同的自然数之和，且使这些自然数的乘积最大。

分享到：
| 是否很久没抽象和逻辑了呢？ DODO它吧(很 ...
评论
9 楼 maozj 2010-07-30  
jellyfish 写道
maozj 写道
20. 最优分解问题。
package boke.written;

/**
 * 20. 最优分解问题。 设n是一个正整数。现在要求将n分解为若干互不相同的自然数之和，且使这些自然数的乘积最大。
 * 贪心算法
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.07
 * 
 */
public class DicompNumber {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 10;
		dicomp(n);

	}

	public static void dicomp(int n) {
		int sum = 1;
		int sun = 0;

		int[] a = new int[n + 1];
		int k = 1;
		if (n < 3) {
			a[1] = 0;
			return;
		}
		if (n < 5) {
			a[k] = 1;
			a[++k] = n - 1;
			return;
		}
		a[1] = 2;
		n -= 2;

		while (n > a[k]) {
			k++;
			a[k] = a[k - 1] + 1;
			n -= a[k];
		}

		if (n == a[k]) {
			a[k]++;
			n--;
		}

		for (int i = 0; i < n; i++) {
			a[k - i]++;
		}
		//
		StringBuffer s = new StringBuffer();
		StringBuffer b = new StringBuffer();
		for (int i = 1; i < a.length; i++) {
			if (a[i] != 0) {
				sun += a[i];
				sum *= a[i];
				s.append(a[i] + " * ");
				b.append(a[i] + " + ");
			}
		}
		String ss = s.substring(0, s.length() - 3);
		String bb = b.substring(0, b.length() - 3);
		ss += " = ";
		bb += " = ";
		ss += sum + "";
		bb += sun + "";

		System.out.println(bb);
		System.out.println(ss);
	}

}


输出：
2 + 3 + 5 = 10
2 * 3 * 5 = 30


10 = 2 + 2 + 2 + 2 + 2
2 * 2 * 2 * 2 * 2 = 32 > 30
???

最优分解问题。 设n是一个正整数。现在要求将n分解为若干互不相同的自然数之和，且使这些自然数的乘积最大。

注意：将n分解为若干互不相同的自然数之和.
8 楼 jellyfish 2010-07-29  
maozj 写道
20. 最优分解问题。
package boke.written;

/**
 * 20. 最优分解问题。 设n是一个正整数。现在要求将n分解为若干互不相同的自然数之和，且使这些自然数的乘积最大。
 * 贪心算法
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.07
 * 
 */
public class DicompNumber {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 10;
		dicomp(n);

	}

	public static void dicomp(int n) {
		int sum = 1;
		int sun = 0;

		int[] a = new int[n + 1];
		int k = 1;
		if (n < 3) {
			a[1] = 0;
			return;
		}
		if (n < 5) {
			a[k] = 1;
			a[++k] = n - 1;
			return;
		}
		a[1] = 2;
		n -= 2;

		while (n > a[k]) {
			k++;
			a[k] = a[k - 1] + 1;
			n -= a[k];
		}

		if (n == a[k]) {
			a[k]++;
			n--;
		}

		for (int i = 0; i < n; i++) {
			a[k - i]++;
		}
		//
		StringBuffer s = new StringBuffer();
		StringBuffer b = new StringBuffer();
		for (int i = 1; i < a.length; i++) {
			if (a[i] != 0) {
				sun += a[i];
				sum *= a[i];
				s.append(a[i] + " * ");
				b.append(a[i] + " + ");
			}
		}
		String ss = s.substring(0, s.length() - 3);
		String bb = b.substring(0, b.length() - 3);
		ss += " = ";
		bb += " = ";
		ss += sum + "";
		bb += sun + "";

		System.out.println(bb);
		System.out.println(ss);
	}

}


输出：
2 + 3 + 5 = 10
2 * 3 * 5 = 30


10 = 2 + 2 + 2 + 2 + 2
2 * 2 * 2 * 2 * 2 = 32 > 30
???
7 楼 zxflb 2010-07-28  
向楼主 学习
6 楼 maozj 2010-06-10  
19. 多处最优服务次序问题。 另外一种解法 

package abstractandlogic;

import java.util.Arrays;

/**
 * 19. 多处最优服务次序问题。 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti， 1<=i<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使
 * 平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。 输入：2个正整数n和s,表示有n个顾客且有s处可以提供顾客需要的服务。
 * 接下来一行中有n个正整数，表式n个顾客需要的服务时间。 输出：最小的平均等待时间
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.08
 * 
 */
public class ManyBestService {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 10;
		int s = 2;
		int[] a = { 56, 12, 1, 99, 1000, 234, 33, 55, 99, 812 };
		double sum = manyBestService(n, s, a);
		System.out.println(sum);
	}

	/**
	 * 求最小的平均等待时间
	 * 
	 * @param n
	 * @param s
	 * @param a
	 * @return
	 */
	public static double manyBestService(int n, int s, int[] a) {
		double sum = 0.0;
		int[] a1 = new int[s];
		int[] a2 = new int[n];

		Arrays.sort(a); // 贪心策略：最短服务时间优先

		int i = 0;
		int j = 0;
		while (i < n) {
			a1[j] += a[i]; // s1处服务时间累加
			a2[i] = a1[j]; // 每个服务员的等待时间

			i++;
			j++;

			if (j == s) {
				j = 0;
			}
		}

		for (i = 0; i < n; i++) {
			sum += a2[i];
		}

		sum /= n; // 最小的平均等待时间

		return sum;
	}

}
5 楼 maozj 2010-06-10  
各位Je朋友， 第19题是相当经典的一道题目，如果你有兴趣，可以好好模拟一下。。。
4 楼 maozj 2010-06-10  

19. 多处最优服务次序问题。
package abstractandlogic;

import java.util.Arrays;

/**
 * 19. 多处最优服务次序问题。 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti， 1<=i<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使
 * 平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。 输入：2个正整数n和s,表示有n个顾客且有s处可以提供顾客需要的服务。
 * 接下来一行中有n个正整数，表式n个顾客需要的服务时间。 输出：最小的平均等待时间
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.08
 * 
 */
public class ManyBestService {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 10;
		int s = 2;
		int[] a = { 56, 12, 1, 99, 1000, 234, 33, 55, 99, 812 };
		double sum = manyBestService(n, s, a);
		System.out.println(sum);
	}
	
	/**
	 * 求最小的平均等待时间
	 * @param n
	 * @param s
	 * @param a
	 * @return
	 */
	public static double manyBestService(int n, int s, int[] a) {
		double sum = 0.0;
		int[] a1 = new int[s];
		int[] a2 = new int[s];

		Arrays.sort(a); // 贪心策略：最短服务时间优先

		int i = 0;
		int j = 0;
		while (i < n) {
			a1[j] += a[i]; // s1处服务时间累加
			a2[j] += a1[j]; // 总的服务时间累加

			i++;
			j++;

			if (j == s) {
				j = 0;
			}
		}

		for (i = 0; i < s; i++) {
			sum += a2[i];
		}

		sum /= n; // 最小的平均等待时间

		return sum;
	}

}
3 楼 maozj 2010-06-10  
18.最优服务次序问题。 

package abstractandlogic;

import java.util.Arrays;

/**
 * 18.最优服务次序问题。 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti， 1<=i<=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?
 * 平均等待时间是n个顾客等待服务时间的总和除以n。 input： 正整数n，表示n个顾客。 接下来一行输入n个正整数，表示n个顾客需要的服务时间。
 * output：最小的平均等待时间
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.08
 * 
 */
public class BestService {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 10;
		int[] a = { 56, 12, 1, 99, 1000, 234, 33, 55, 99, 812 };
		double sum = bestService(a, n);
		System.out.println(sum);

	}

	/**
	 * 计算最小的平均等待时间
	 * 
	 * @param a
	 * @param n
	 * @return
	 */
	public static double bestService(int[] a, int n) {
		double sum = 0.0;
		Arrays.sort(a); // 贪心策略：最短服务时间优先

		for (int i = 1; i < n; i++) {
			a[i] += a[i - 1];
		}

		for (int i = 0; i < n; i++) {
			sum += a[i];
		}

		sum /= n; // 最小的平均等待时间

		return sum;
	}

}
2 楼 maozj 2010-06-09  
17. 字符统计问题。 

package abstractandlogic;

import java.util.HashMap;
import java.util.Map;

/**
 * 17. 字符统计问题。 编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。
 * 
 * @sincejdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.08
 * 
 */
public class CharacterFrequency {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		characterFrequency("ab");

	}

	/**
	 * 统计不同字符出现的频度
	 * 
	 * @param s
	 */
	public static void characterFrequency(String s) {
		Map<Character, Integer> charMap = new HashMap<Character, Integer>();
		if (s != null && !"".equals(s)) {
			char[] ch = s.toCharArray();
			int len = ch.length;

			for (char c : ch) {
				if (charMap.containsKey(c)) {
					int i = charMap.get(c);
					i++;
					charMap.put(c, i);
				} else {
					charMap.put(c, 1);
				}
			}

			for (Map.Entry<Character, Integer> entry : charMap.entrySet()) {
				char c = entry.getKey();
				int i = entry.getValue();
				System.out.println(c + " : " + i);
			}

		}
	}

}
1 楼 maozj 2010-06-08  
20. 最优分解问题。
package boke.written;

/**
 * 20. 最优分解问题。 设n是一个正整数。现在要求将n分解为若干互不相同的自然数之和，且使这些自然数的乘积最大。
 * 贪心算法
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.07
 * 
 */
public class DicompNumber {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 10;
		dicomp(n);

	}

	public static void dicomp(int n) {
		int sum = 1;
		int sun = 0;

		int[] a = new int[n + 1];
		int k = 1;
		if (n < 3) {
			a[1] = 0;
			return;
		}
		if (n < 5) {
			a[k] = 1;
			a[++k] = n - 1;
			return;
		}
		a[1] = 2;
		n -= 2;

		while (n > a[k]) {
			k++;
			a[k] = a[k - 1] + 1;
			n -= a[k];
		}

		if (n == a[k]) {
			a[k]++;
			n--;
		}

		for (int i = 0; i < n; i++) {
			a[k - i]++;
		}
		//
		StringBuffer s = new StringBuffer();
		StringBuffer b = new StringBuffer();
		for (int i = 1; i < a.length; i++) {
			if (a[i] != 0) {
				sun += a[i];
				sum *= a[i];
				s.append(a[i] + " * ");
				b.append(a[i] + " + ");
			}
		}
		String ss = s.substring(0, s.length() - 3);
		String bb = b.substring(0, b.length() - 3);
		ss += " = ";
		bb += " = ";
		ss += sum + "";
		bb += sun + "";

		System.out.println(bb);
		System.out.println(ss);
	}

}


输出：
2 + 3 + 5 = 10
2 * 3 * 5 = 30
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    PHPWind dodostyle模板

    PHPWind dodostyle模板

    DODO研究所-NFT 全景解析｜历史、当下和未来.rar

    DODO研究所-NFT 全景解析｜历史、当下和未来

    PHP整站打包程序-By DoDo

    PHP整站打包程序-By DoDo 小巧、快捷、推荐！

    林dodo.zip

    林dodo.zip

    Dodo_apktool.zip

    Dodo_apktool.zip

    dodo-smart-contract

    DODO：流动性比未拆单高10倍 什么是DODO？ :writing_hand: DODO基于全新的做市商算法，其基本思想是风险中立，以保持流动性提供者的投资组合稳定。 与AMM相比，DODO的流动性要好10倍。 谁审核DODO？ 是一家领先...

    Dodo_apktool

    因为安卓系统是开源的所以给我们自己个性化手机带来了很大的便利。不需要进行复杂的破解等操作甚至只需要几个简单的小软件我们就可以制作一个属于自己的ROM。下面这个就是apk文件的反编译工具和签名工具

    dodo锁屏主题

    一块锁屏主题，很漂亮的相信大家一定会喜欢的

    DoDo:Android手机的ToDo应用程序

    任务/待办事项保存我在代码中如何称呼它们的简单待办事项和“任务”是DoDo的一项功能。 一些简单的文本，带有用于将项目标记为已完成的复选框，一个编辑按钮和一个删除按钮。 所有这些都将显示在列表中。 每个任务的...

    dodo_apktool反编译工具

    android反编译工具，带UI界面，可签名

    Dodo

    渡渡鸟

    dodo.js:基于Javascript Pixi的游戏开发库

    dodo.js Javascript游戏引擎 Dodo.js是一个新生的轻量级（&lt;500K）javascript游戏引擎。 该框架依赖 Underscore.js，“有用的函数式编程助手” PIXI用于图形处理 ... 但是，它可以很容易地扩展到中等规模的项目。

    DoDo.API

    待办事项后端 DoDo的服务器端代码-您的任务和时间管理器！

    Dodo APK Tools(Android程序反编译器)

    Dodo APK Tools(Android程序反编译器)绿色版 老外写的《android-apktool》软件，可以帮助我们把APK反编译，生成程序的源代码和图片、XML配置、语言资源等文件。我们对图片和语言资源等文件修改后，可以再把它们编译...

    Python库 | dodo-0.1.tar.gz

    python库。资源全名：dodo-0.1.tar.gz

    dodo:小技巧和任务

    dodo:小技巧和任务

    DoDo(兜兜)截屏缩放大师(豪华版) 7.0.0.zip

    DoDo(兜兜)截屏缩放大师(豪华版)[V 7.0.0 免费]。 　1、此版免费。 　2、支持捐助。 　详细介绍： 　中国辽宁大连，鑫信软件全力打造的，经典大众软件之一。简单的说，就是截屏大师和缩放大师二合一软件。 　...

    DoDo(兜兜)录音摄像大师(豪华版) 7.0.0.zip

    DoDo（兜兜）录音摄像大师（豪华版）。 　1、此号版本免费。 　2、支持购买捐助。 　详细介绍： 　中国辽宁大连，鑫信软件全力打造的，经典大众软件之一。简单的说，就是录音大师和摄像大师二合一软件 　目前...

    动物内容聚合站The DoDo：将萌宠进行到底.docx

    动物内容聚合站The DoDo：将萌宠进行到底.docx

Magicbox
Global site tag (gtag.js) - Google Analytics