2009-05-08, 03:06
#1
Jag sitter här med en läxa som jag har riktigt svårt att klura ut. Det är framförallt logiken som är problemet men jag kanske kommer behöva hjälp med kodningen också. Tack på förhand
Uppgiften (är bifogad i sin helhet längre ner) är att räkna ut antalet möjliga tal som kan ha kommit från en miniräknare som saknar display. Jag måste använda mig av Lists, som jag inte har en aning om hur vanliga dom är i Sverige (En List är en serie av nodes som är sammankopplade på såvis att den föregående pekar på nästa och den i sin tur pekar på nästa osv. Jag bifogar hela List classen längre ner)
Vad jag har gjort hitilst:
Här är definitionen av nodes och även List(Sorry för texten mitt i):
Och här är själva uppgiften:
HW#7 SPECS
==========
In your HW7 program code, you must use ONLY Linked List data structures,
i.e. use the List.java file from the online lecture notes.
You must NOT use non-List data structures (e.g., arrays, etc).
(Unless, they are only used to store Lists, such as described in the
"Extra Hint" below.)
Speed requirements:
Your program must compute and output the answer in less than 5 seconds (on rohan).
HINT:
Don't compute and check all possible combinations after the
user has inputted his or her data. There are over 31 billion combinations,
so examining them individually will result in large running times.
Instead, you can decrease your program's running time by figuring out
clever ways to decrease the number of combinations you must examine.
E.g., you can speed up your program's running time by pre-computing and storing
relevant information ahead of time (in List data structures).
SAMPLE RUN:
rohan% javac HW7.java
rohan% java HW7
Input X's milliamps: <--- assume user enters 30
Input Y's milliamps: <--- assume user enters 65
Input Z's milliamps: <--- assume user enters 65
Possible solutions = 819
---------------------------------------------------------------------------
EXTRA HINT
==========
One way, to tackle HW7:
Create an array which contains 23 List objects, i.e. lists[0] to lists[22].
Check all the integers from -999 to 999.
For each of those integers, compute the number of calculator "segments", k,
required for it.
Insert at the back of lists[k], the object equivalent of the current integer.
(You have to store objects, e.g. Strings, since Lists store Objects not ints.)
---------------------------------------------------------------------------
[Problem is from Association for Computing Machinery, 2008-2009.]
Patrick has a four function calculator (add, subtract, multiply, divide). Unfortunately, the display is broken, but the calculator still functions. This calculator has a display constructed from "seven-segment" digits.
This particular calculator only displays three digits of accuracy:
integers from -999 to 999, inclusive. There are no decimal points since all math is performed using integers (with truncation for the divisions).
[Truncation means remove the fraction, don't round up or down. I.e., the calculator's division works like Java's "int/int" division.]
Example: the number -112 lights up ten segments (2 segments for the "1", 2 segments for the next "1", 5 segments for the "2", plus 1 extra segment for the "-" sign).
(Like on real calculators, negative numbers get a "-", but there's no "+" sign in front of positive numbers which are displayed.)
(For ease, assume that no value will ever contain numbers with leading zeroes.)
In order to prove that the calculator still operates, the back cover is removed and an ammeter is attached to the display. An ammeter measures the current consumed by the device, and each segment of a digit consumes five milliamps per segment. Thus, to display a number such as "798" the current consumption can be predicted as follows:
Digit 7: 3 segments lit = 15 milliamps
Digit 9: 6 segments lit = 30 milliamps
Digit 8: 7 segments lit = 35 milliamps
Total = 80 milliamps
Of course, the number "798" consumes the same amount of current as "897", or "-891", etc.
Patrick wishes to prove that the functionality of the calculator is intact, so he enters "949" and measures 80 milliamps. Then he pushes the subtract key. Next he enters "51" and measures 35 milliamps. After pressing the "=" key, the result should be "898", measuring 100 milliamps.
As a second example, he enters "-5", then pushes the addition key. He then enters "-4" and presses equal. The answer is "-9". The measurements were 30 milliamps, 25 milliamps, and 35 milliamps.
Patrick is now presented with the following problem:
Given the current consumption (milliamps) of operand X, operand Y, and result Z, and given unknown operation Op (either +, -, *, or /), determine the number of possible solutions (if any) for
X Op Y = Z
Note that in all cases there are only three digits on the display. Although the input values of 80, 35, and 100 potentially could represent 949*13 = 12337, this is not possible because 12337 is too large for the three digit display to hold.
Example:
If the user inputs values of X's milliamps=25, Y's milliamps=25, Z's milliamps=20, your program should output 5, since there are 5 possible results:
-11 - -4 = -7
-4 - 3 = -7
2 + 2 = 4
2 * 2 = 4
71 / 17 = 4
Some input combinations have no result. For example, for the values 35, 10, 10 there is no possible answer (since there are no leading zeroes).
Your program's input will only consist of positive integer values for X's milliamps, Y's milliamps, Z's milliamps.
For the user's input, your program is to determine the number of possible solutions and output that number.
Sample Inputs and Outputs
25 25 20 ---> should output 5
35 10 10 ---> should output 0
15 20 30 ---> should output 9
30 65 65 ---> should output 819
Seven-segment display
The digits
Uppgiften (är bifogad i sin helhet längre ner) är att räkna ut antalet möjliga tal som kan ha kommit från en miniräknare som saknar display. Jag måste använda mig av Lists, som jag inte har en aning om hur vanliga dom är i Sverige (En List är en serie av nodes som är sammankopplade på såvis att den föregående pekar på nästa och den i sin tur pekar på nästa osv. Jag bifogar hela List classen längre ner)
Vad jag har gjort hitilst:
Kod:
import sdsu.io*;
public class HW7
{
public static List[] list = new List[23];
int x = Console.readLine("Input X's milliamps");
int y = Console.readLine("Input Y's milliamps");
int z = Console.readLine("inout Z's milliamps");
x = x / 5;
y = y / 5;
z = z / 5;
}
Här är definitionen av nodes och även List(Sorry för texten mitt i):
Kod:
// List.java
class Node
{
public Object data;
public Node next;
public Node()
{
this.data = null;
this.next = null;
}
public Node(Object a)
{
this.data = a;
this.next = null;
}
public Node(Object a, Node b)
{
this.data = a;
this.next = b;
}
} //end Node class
public class List
{
private Node head;
private Node tail;
public List()
{
this.head = null;
this.tail = null;
}
//-------------------------
public void insertAtFront(Object obj)
{
if (this.size()==0)
{
Node n = new Node(obj);
this.head = n;
this.tail = n;
}
else
{
Node n = new Node(obj);
n.next = this.head;
this.head = n;
}
}
//----------------------------
public void insertAtBack(Object obj)
{
if (this.size()==0)
{
Node n = new Node(obj);
this.head = n;
this.tail = n;
}
else
{
Node n = new Node(obj);
this.tail.next = n;
this.tail = n;
}
}
//------------------------------
public Object removeFromFront()
{
if (this.size()==0)
{
System.out.println("No data to remove.");
return null;
}
else if (this.size()==1)
{
Object a = this.head.data;
this.head = null;
this.tail = null;
return a;
}
else
{
Object a = this.head.data;
this.head = this.head.next;
return a;
}
}
//-----------------------------
public Object removeFromBack()
{
if (this.size()==0)
{
System.out.println("No data to remove.");
return null;
}
else if (this.size()==1)
{
Object a = this.tail.data;
this.head = null;
this.tail = null;
return a;
}
else
{
Object a = this.tail.data;
Node ntlnode = this.head;
while (ntlnode.next != this.tail)
{
ntlnode = ntlnode.next;
}
this.tail = ntlnode;
this.tail.next = null;
return a;
}
}
//-------------------------
public boolean isEmpty()
{
return this.head == null;
//or: return this.size()==0;
}
public void print()
{
if (this.size()==0)
{
System.out.println("Empty list!");
return;
}
Node curr = this.head; //start at the front of the list.
while (curr != null)
{
System.out.println(curr.data.toString()); //print current data item.
curr = curr.next; //move forward to the next data item.
}
System.out.println();
}
//-------------------------
public int size()
{
int count = 0;
//the WHILE loop will "roller coaster" through ALL nodes in the list,
//counting each one. size() will work correctly even for an empty list.
Node curr = this.head; //start at the front of the list.
while (curr != null)
{
count++; //count current data item.
curr = curr.next; //move forward to the next data item.
}
return count;
}
//-------------------------
} //end List class
Och här är själva uppgiften:
HW#7 SPECS
==========
In your HW7 program code, you must use ONLY Linked List data structures,
i.e. use the List.java file from the online lecture notes.
You must NOT use non-List data structures (e.g., arrays, etc).
(Unless, they are only used to store Lists, such as described in the
"Extra Hint" below.)
Speed requirements:
Your program must compute and output the answer in less than 5 seconds (on rohan).
HINT:
Don't compute and check all possible combinations after the
user has inputted his or her data. There are over 31 billion combinations,
so examining them individually will result in large running times.
Instead, you can decrease your program's running time by figuring out
clever ways to decrease the number of combinations you must examine.
E.g., you can speed up your program's running time by pre-computing and storing
relevant information ahead of time (in List data structures).
SAMPLE RUN:
rohan% javac HW7.java
rohan% java HW7
Input X's milliamps: <--- assume user enters 30
Input Y's milliamps: <--- assume user enters 65
Input Z's milliamps: <--- assume user enters 65
Possible solutions = 819
---------------------------------------------------------------------------
EXTRA HINT
==========
One way, to tackle HW7:
Create an array which contains 23 List objects, i.e. lists[0] to lists[22].
Check all the integers from -999 to 999.
For each of those integers, compute the number of calculator "segments", k,
required for it.
Insert at the back of lists[k], the object equivalent of the current integer.
(You have to store objects, e.g. Strings, since Lists store Objects not ints.)
---------------------------------------------------------------------------
[Problem is from Association for Computing Machinery, 2008-2009.]
Patrick has a four function calculator (add, subtract, multiply, divide). Unfortunately, the display is broken, but the calculator still functions. This calculator has a display constructed from "seven-segment" digits.
This particular calculator only displays three digits of accuracy:
integers from -999 to 999, inclusive. There are no decimal points since all math is performed using integers (with truncation for the divisions).
[Truncation means remove the fraction, don't round up or down. I.e., the calculator's division works like Java's "int/int" division.]
Example: the number -112 lights up ten segments (2 segments for the "1", 2 segments for the next "1", 5 segments for the "2", plus 1 extra segment for the "-" sign).
(Like on real calculators, negative numbers get a "-", but there's no "+" sign in front of positive numbers which are displayed.)
(For ease, assume that no value will ever contain numbers with leading zeroes.)
In order to prove that the calculator still operates, the back cover is removed and an ammeter is attached to the display. An ammeter measures the current consumed by the device, and each segment of a digit consumes five milliamps per segment. Thus, to display a number such as "798" the current consumption can be predicted as follows:
Digit 7: 3 segments lit = 15 milliamps
Digit 9: 6 segments lit = 30 milliamps
Digit 8: 7 segments lit = 35 milliamps
Total = 80 milliamps
Of course, the number "798" consumes the same amount of current as "897", or "-891", etc.
Patrick wishes to prove that the functionality of the calculator is intact, so he enters "949" and measures 80 milliamps. Then he pushes the subtract key. Next he enters "51" and measures 35 milliamps. After pressing the "=" key, the result should be "898", measuring 100 milliamps.
As a second example, he enters "-5", then pushes the addition key. He then enters "-4" and presses equal. The answer is "-9". The measurements were 30 milliamps, 25 milliamps, and 35 milliamps.
Patrick is now presented with the following problem:
Given the current consumption (milliamps) of operand X, operand Y, and result Z, and given unknown operation Op (either +, -, *, or /), determine the number of possible solutions (if any) for
X Op Y = Z
Note that in all cases there are only three digits on the display. Although the input values of 80, 35, and 100 potentially could represent 949*13 = 12337, this is not possible because 12337 is too large for the three digit display to hold.
Example:
If the user inputs values of X's milliamps=25, Y's milliamps=25, Z's milliamps=20, your program should output 5, since there are 5 possible results:
-11 - -4 = -7
-4 - 3 = -7
2 + 2 = 4
2 * 2 = 4
71 / 17 = 4
Some input combinations have no result. For example, for the values 35, 10, 10 there is no possible answer (since there are no leading zeroes).
Your program's input will only consist of positive integer values for X's milliamps, Y's milliamps, Z's milliamps.
For the user's input, your program is to determine the number of possible solutions and output that number.
Sample Inputs and Outputs
25 25 20 ---> should output 5
35 10 10 ---> should output 0
15 20 30 ---> should output 9
30 65 65 ---> should output 819
Seven-segment display
The digits
