Brian Warehouse

You are given natural numbers a and b. Find a^b-b^a.

Input contains numbers a and b (1≤a,b≤100).

Write answer to output.

Sample Input

2 3

Sample Output

-1

一看到这种题目，就想到高精度算法，Java的大数。
此举确实流氓了一点，不过确实过了，鄙人的第一题SGU啊，不许打击。
过段时间看看能不能写出 (C++ Edition) ,啥也别说了，上代码。

import java.math.*;
import java.util.*;

public class Solution
{
   public static void main(String[] args)
   {
      Scanner in = new Scanner(System.in);
      int a = in.nextInt();
      int b = in.nextInt();
      
      BigInteger A=BigInteger.valueOf(a);
      BigInteger B=BigInteger.valueOf(b); // A^B
      BigInteger rA=BigInteger.valueOf(a);
      BigInteger rB=BigInteger.valueOf(b); // store the result after computing
      
      for(int i=1; i<b; i++) // just b-1 times
          rA=rA.multiply(A);
      for(int i=1; i<a; i++)    
          rB=rB.multiply(B);
      System.out.println(rA.subtract(rB)); // sub
   }
}

附《Core Java I》里关于 大数的简单介绍，讲的算比较清晰的了：
Big Numbers
If the precision of the basic integer and floating-point types is not sufficient, you can
turn to a couple of handy classes in the java.math package: BigInteger and BigDecimal. These
are classes for manipulating numbers with an arbitrarily long sequence of digits. The
BigInteger class implements arbitrary precision integer arithmetic, and BigDecimal does the
same for floating-point numbers.
Use the static valueOf method to turn an ordinary number into a big number:
BigInteger a = BigInteger.valueOf(100);
Unfortunately, you cannot use the familiar mathematical operators such as + and * to
combine big numbers. Instead, you must use methods such as add and multiply in the big
number classes.
BigInteger c = a.add(b); // c = a + b
BigInteger d = c.multiply(b.add(BigInteger.valueOf(2))); // d = c * (b + 2)
C++ NOTE: Unlike C++, Java has no programmable operator overloading. There was no way
for the programmer of the BigInteger class to redefine the + and * operators to give the add and
multiply operations of the BigInteger classes. The language designers did overload the + operator
to denote concatenation of strings. They chose not to overload other operators, and they
did not give Java programmers the opportunity to overload operators in their own classes.
Listing 3–6 shows a modification of the lottery odds program of Listing 3–5, updated to
work with big numbers. For example, if you are invited to participate in a lottery in
which you need to pick 60 numbers out of a possible 490 numbers, then this program
will tell you that your odds are 1 in 7163958434619955574151162225400929334117176
12789263493493351 013459481104668848. Good luck!
The program in Listing 3–5 computed the statement
lotteryOdds = lotteryOdds * (n - i + 1) / i;
When big numbers are used, the equivalent statement becomes
lotteryOdds = lotteryOdds.multiply(BigInteger.valueOf(n - i + 1)).divide(BigInteger.valueOf(i));
Listing 3–6 BigIntegerTest.java
1. import java.math.*;
2. import java.util.*;
3.
4. /**
5. * This program uses big numbers to compute the odds of winning the grand prize in a lottery.
6. * @version 1.20 2004-02-10
7. * @author Cay Horstmann
8. */
9. public class BigIntegerTest
10. {
11. public static void main(String[] args)
12. {
13. Scanner in = new Scanner(System.in);
14.
15. System.out.print("How many numbers do you need to draw? ");
16. int k = in.nextInt();
17.
18. System.out.print("What is the highest number you can draw? ");
19. int n = in.nextInt();
20.
21. /*
22. * compute binomial coefficient n*(n-1)*(n-2)*...*(n-k+1)/(1*2*3*...*k)
23. */
24.
25. BigInteger lotteryOdds = BigInteger.valueOf(1);
26.
27. for (int i = 1; i <= k; i++)
28. lotteryOdds = lotteryOdds.multiply(BigInteger.valueOf(n - i + 1)).divide(
29. BigInteger.valueOf(i));
30.
31. System.out.println("Your odds are 1 in " + lotteryOdds + ". Good luck!");
32. }
33. }

java.math.BigInteger

? BigInteger add(BigInteger other)
? BigInteger subtract(BigInteger other)
? BigInteger multiply(BigInteger other)
? BigInteger divide(BigInteger other)
? BigInteger mod(BigInteger other)
returns the sum, difference, product, quotient, and remainder of this big integer and
other.
? int compareTo(BigInteger other)
returns 0 if this big integer equals other, a negative result if this big integer is less
than other, and a positive result otherwise.
? static BigInteger valueOf(long x)
returns a big integer whose value equals x.
? BigDecimal add(BigDecimal other)
? BigDecimal subtract(BigDecimal other)
? BigDecimal multiply(BigDecimal other)
? BigDecimal divide(BigDecimal other, RoundingMode mode) 5.0
returns the sum, difference, product, or quotient of this big decimal and other.
To compute the quotient, you must supply a rounding mode. The mode
RoundingMode.HALF_UP is the rounding mode that you learned in school (i.e., round
down digits 0 . . . 4, round up digits 5 . . . 9). It is appropriate for routine
calculations. See the API documentation for other rounding modes.
? int compareTo(BigDecimal other)
returns 0 if this big decimal equals other, a negative result if this big decimal is less
than other, and a positive result otherwise.
? static BigDecimal valueOf(long x)
? static BigDecimal valueOf(long x, int scale)
returns a big decimal whose value equals x or x /10scale.

一、实验内容

利用高级语言，设计一个采用二级或二级以上的多级文件目录管理系统，实现对文件的基本操作，如：文件的建立、打开、关闭、复制、撤销、检索等。

二、实验目的

用高级语言编写和调试一个简单的文件系统，模拟文件管理的工作过程。从而对各种文件操作命令的实质内容和执行过程有比较深入的了解。

要求设计一个 n个用户的文件系统，每次用户可保存m个文件，用户在一次运行中只能打开一个文件，对

文件必须设置保护措施，且至少有Create、delete、open、close、read、write等命令。

三、实验环境

1．PC微机。

2．Windows 操作系统。

3．C/C++/VB开发集成环境。

四、实验题目

设计一个10个用户的文件系统，每次用户可保存10个文件，一次运行用户可以打开5个文件。 程序采用二级文件目录（即设置主目录[MFD]）和用户文件目录（UED）。另外，为打开文件设置了运行文件目录（AFD）。 为了便于实现，对文件的读写作了简化，在执行读写命令时，只需改读写指针，并不进行实际的读写操作。

算法设计思想：

（1）       因系统小，文件目录的检索使用了简单的线性搜索。

（2）       文件保护简单使用了三位保护码：允许读写执行、对应位为 1，对应位为0，则表示不允许读写、执行。

（3）       程序中使用的主要设计结构如下：

主文件目录和用户文件目录（ MFD、UFD），  打开文件目录（ AFD）（即运行文件目录）

一、实验内容

利用高级语言模拟进程的时间片轮转调度算法，响应比高者优先调度算法。

二、实验目的

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。

三、实验环境

1．PC微机。

2．Windows 操作系统。

3．C/C++/VB开发集成环境。

四、实验题目

本实验有两个小题。

第一题：设计一个按时间片轮转法实现处理器调度的程序。

算法设计思想：

(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：

其中，进程名——作为进程的标识，假设五个进程的进程名分别为Q₁，Q₂，Q₃，Q₄，Q₅。

指针——进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。

要求运行时间——假设进程需要运行的单位时间数。

已运行时间——假设进程已经运行的单位时间数，初始值为“0”。

状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。

(2) 每次运行所设计的进程调度程序前，为每个进程任意确定它的“要求运行时间”。

(3) 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如，当前轮到P₂执行，则有：

标志单元

         K₂   

(4) 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：

已运行时间+1

来模拟进程的一次运行，表示进程已经运行过一个单位的时间。

请注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已经运行满一个时间片。

(5) 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间?已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。

(6) 若“就绪”状态的进程队列不为空，则重复上面的（4）和（5）的步骤，直到所有的进程都成为“结束”状态。

(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。

(8) 为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。

第二题：设计一个按响应比高者优先调度算法实现进程调度的程序。

算法设计思想：

 (1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：

其中，进程名——作为进程的标识，假设五个进程的进程名分别为P₁，P₂，P₃，P₄，P₅。

指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。

要求运行时间——假设进程需要运行的单位时间数。

等待时间——自最近一次调度运行至今等待的时间数，当进程被调度时等待时间清零。

响应比——进程调度程序运行前计算每个进程的响应比，调度时总是选取响应比大的进程先执行，每次执行一个固定的时间片。

状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。

(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“等待时间”和“要求运行时间”。

(3) 为了调度方便，把五个进程按给定的响应比从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例：

  队首标志

         K₂   

(4) 处理器调度总是选队首进程运行。采用动态改变响应比的办法，进程每运行一次重新计算各进程的响应比。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：要求运行时间-1、等待时间为0。其它进程等待时间+1，重新计算各进程的响应比，并从大到小排序。

提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。

(5) 进程运行一次后，若要求运行时间?0，则再将它加入队尾（因其响应比最小。）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。

(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。

(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化及各进程的参数。

本学期学习了操作系统，实验课共有三个大实验，共有五个题目：时间片轮转法、高响应比优先、首次适应算法、位示图法、文件管理。每部分都会附上实验指导书和代码。每个实验都有点问题，请大家指教。

还有就是要提醒一下找到这里的学弟学妹，火哥可是知道我写代码的风格的，这些代码他也都看过，如果要用在实验作业上，请你们三思。

如果你们原封不动的复制粘贴，那就太令我失望了，师大的学风要上来啊。