SHARE
TWEET

Колоквиумска АПС - Сума на два големи броеви (Листи)

a guest Feb 21st, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. class DLLNode<E> {
  4.     protected E element;
  5.     protected DLLNode<E> pred, succ;
  6.  
  7.     public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  8.         this.element = elem;
  9.         this.pred = pred;
  10.         this.succ = succ;
  11.     }
  12.  
  13.     @Override
  14.     public String toString() {
  15.         return element.toString();
  16.     }
  17. }
  18.  
  19.  
  20. class DLL<E> {
  21.     private DLLNode<E> first, last;
  22.  
  23.     public DLL() {
  24.         // Construct an empty SLL
  25.         this.first = null;
  26.         this.last = null;
  27.     }
  28.  
  29.     public void deleteList() {
  30.         first = null;
  31.         last = null;
  32.     }
  33.    
  34.     public int length() {
  35.         int ret;
  36.         if (first != null) {
  37.             DLLNode<E> tmp = first;
  38.             ret = 1;
  39.             while (tmp.succ != null) {
  40.                 tmp = tmp.succ;
  41.                 ret++;
  42.             }
  43.             return ret;
  44.         } else
  45.             return 0;
  46.  
  47.     }
  48.  
  49.     public DLLNode<E> find(E o) {
  50.         if (first != null) {
  51.             DLLNode<E> tmp = first;
  52.             while (tmp.element != o && tmp.succ != null)
  53.                 tmp = tmp.succ;
  54.             if (tmp.element == o) {
  55.                 return tmp;
  56.             } else {
  57.                 System.out.println("Elementot ne postoi vo listata");
  58.             }
  59.         } else {
  60.             System.out.println("Listata e prazna");
  61.         }
  62.         return first;
  63.     }
  64.    
  65.     public void insertFirst(E o) {
  66.         DLLNode<E> ins = new DLLNode<E>(o, null, first);
  67.         if (first == null)
  68.             last = ins;
  69.         else
  70.             first.pred = ins;
  71.         first = ins;
  72.     }
  73.  
  74.     public void insertLast(E o) {
  75.         if (first == null)
  76.             insertFirst(o);
  77.         else {
  78.             DLLNode<E> ins = new DLLNode<E>(o, last, null);
  79.             last.succ = ins;
  80.             last = ins;
  81.         }
  82.     }
  83.  
  84.     public void insertAfter(E o, DLLNode<E> after) {
  85.         if(after==last){
  86.             insertLast(o);
  87.             return;
  88.         }
  89.         DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  90.         after.succ.pred = ins;
  91.         after.succ = ins;
  92.     }
  93.  
  94.     public void insertBefore(E o, DLLNode<E> before) {
  95.         if(before == first){
  96.             insertFirst(o);
  97.             return;
  98.         }
  99.         DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  100.         before.pred.succ = ins;
  101.         before.pred = ins;
  102.     }
  103.  
  104.     public E deleteFirst() {
  105.         if (first != null) {
  106.             DLLNode<E> tmp = first;
  107.             first = first.succ;
  108.             if (first != null) first.pred = null;
  109.             if (first == null)
  110.                 last = null;
  111.             return tmp.element;
  112.         } else
  113.             return null;
  114.     }
  115.  
  116.     public E deleteLast() {
  117.         if (first != null) {
  118.             if (first.succ == null)
  119.                 return deleteFirst();
  120.             else {
  121.                 DLLNode<E> tmp = last;
  122.                 last = last.pred;
  123.                 last.succ = null;
  124.                 return tmp.element;
  125.             }
  126.         }
  127.         // else throw Exception
  128.         return null;
  129.     }
  130.  
  131.     public E delete(DLLNode<E> node) {
  132.         if(node==first){
  133.             deleteFirst();
  134.             return node.element;
  135.         }
  136.         if(node==last){
  137.             deleteLast();
  138.             return node.element;
  139.         }
  140.         node.pred.succ = node.succ;
  141.         node.succ.pred = node.pred;
  142.         return node.element;
  143.        
  144.     }
  145.  
  146.     @Override
  147.     public String toString() {
  148.         String ret = new String();
  149.         if (first != null) {
  150.             DLLNode<E> tmp = first;
  151.             ret += tmp;
  152.             while (tmp.succ != null) {
  153.                 tmp = tmp.succ;
  154.                 ret += tmp;
  155.             }
  156.         } else
  157.             ret = "Prazna lista!!!";
  158.         return ret;
  159.     }
  160.    
  161.     public String toStringR() {
  162.         String ret = new String();
  163.         if (last != null) {
  164.             DLLNode<E> tmp = last;
  165.             ret += tmp + "<->";
  166.             while (tmp.pred != null) {
  167.                 tmp = tmp.pred;
  168.                 ret += tmp + "<->";
  169.             }
  170.         } else
  171.             ret = "Prazna lista!!!";
  172.         return ret;
  173.     }
  174.  
  175.     public DLLNode<E> getFirst() {
  176.         return first;
  177.     }
  178.  
  179.     public DLLNode<E> getLast() {
  180.  
  181.         return last;
  182.     }
  183.    
  184.     public void izvadiDupliIPrebroj(){
  185.        
  186.     }
  187. }
  188. public class BigNumbers {
  189.  
  190.     public static void calculate(DLL<Integer> lista1, DLL<Integer> lista2)
  191.     {
  192.         DLLNode<Integer> tmp1 = lista1.getFirst();
  193.         DLLNode<Integer> tmp2 = lista2.getFirst();
  194.        
  195.         DLL<Integer> lista = new DLL<Integer>();
  196.        
  197.         int sum=0;
  198.         int prva=0;
  199.        
  200.        
  201.         while(tmp1!=null && tmp2!=null)
  202.         {
  203.             sum=0;
  204.             sum = tmp1.element + tmp2.element + prva;
  205.            
  206.             if(sum>9)
  207.             {
  208.                 int posledna=0;
  209.                 prva=0;
  210.                
  211.                 prva=sum/10;
  212.                 posledna=sum%10;
  213.                
  214.                 lista.insertFirst(posledna);
  215.                 if(tmp1.succ!=null) tmp1=tmp1.succ;
  216.                 else break;
  217.                 if(tmp2.succ!=null) tmp2=tmp2.succ;
  218.                 else break;
  219.                
  220.             }
  221.                
  222.             else
  223.             {
  224.                 lista.insertFirst(sum);
  225.                 prva=0;
  226.                 if(tmp1.succ!=null) tmp1=tmp1.succ;
  227.                 else break;
  228.                 if(tmp2.succ!=null) tmp2=tmp2.succ;
  229.                 else break;
  230.             }
  231.            
  232.         }
  233.    
  234.            
  235.        
  236.        
  237.        
  238.         if(tmp1.succ!=null)  //go dodadov succ
  239.         {
  240.            
  241.             while(tmp1!=null)
  242.             {
  243.            
  244.                
  245.                 if(prva==0)
  246.                 {
  247.                     lista.insertFirst(tmp1.element);
  248.                     if(tmp1.succ!=null) tmp1=tmp1.succ;
  249.                     else break;
  250.                    
  251.                 }
  252.                else {
  253.                 if(tmp1.element + prva >9)
  254.                 {
  255.                     int posledna=0;
  256.                     //prva=0; //neee
  257.                    
  258.                     prva=(tmp1.element + prva)/10;
  259.                     posledna=(tmp1.element + prva)%10;
  260.                    
  261.                     lista.insertFirst(posledna);
  262.                     if(tmp1.succ!=null) tmp1=tmp1.succ;
  263.                     else break;
  264.                    
  265.                    
  266.                    
  267.                 }
  268.                    
  269.                 else
  270.                 {
  271.                     lista.insertFirst(tmp1.element + prva);
  272.                     prva=0;
  273.                     if(tmp1.succ!=null) tmp1=tmp1.succ;
  274.                     else break;
  275.                    
  276.                    
  277.                 }
  278.                
  279.             }
  280.                
  281.             }
  282.                
  283.         }
  284.        
  285.         if(tmp2.succ!=null)   //go dodadov succ
  286.         {
  287.             tmp2=tmp2.succ; //i ova, zoshto ako prvata e pokratka, ovoj node nema da se stavi na negoviot succ
  288.             while(tmp2!=null)
  289.             {
  290.            
  291.                 if(prva==0)
  292.                 {
  293.                     lista.insertFirst(tmp2.element);
  294.                     if(tmp2.succ!=null) tmp2=tmp2.succ;
  295.                     else break;
  296.                    
  297.                 }
  298.                else {
  299.                 if(tmp2.element + prva >9)
  300.                 {
  301.                     int posledna=0;
  302.                     //prva=0; //neee
  303.                    
  304.                     prva=(tmp2.element + prva)/10;
  305.                     posledna=(tmp2.element + prva)%10;
  306.                    
  307.                     lista.insertFirst(posledna);
  308.                     if(tmp2.succ!=null) tmp2=tmp2.succ;
  309.                     else break;
  310.                    
  311.                    
  312.                 }
  313.                    
  314.                 else
  315.                 {
  316.                     lista.insertFirst(tmp2.element + prva);
  317.                     prva=0;
  318.                     if(tmp2.succ!=null) tmp2=tmp2.succ;
  319.                     else break;
  320.                    
  321.                 }
  322.             }
  323.                
  324.                
  325.             }
  326.            
  327.                
  328.         }
  329.        
  330.    
  331.    
  332.        
  333.  
  334.         if(prva!=0) lista.insertFirst(1); //go dodadov ovoj red
  335.        
  336.         System.out.println(lista.toString());
  337.        
  338.        
  339.     }
  340.    
  341.     public static void main(String[] args) {
  342.         Scanner scan = new Scanner(System.in);
  343.        
  344.         String prv = scan.nextLine();
  345.         String vtor = scan.nextLine();
  346.        
  347.         DLL<Integer> lista1 = new DLL<Integer>();
  348.         DLL<Integer> lista2 = new DLL<Integer>();
  349.        
  350.         char [] cifri1 = prv.toCharArray();
  351.         char [] cifri2 = vtor.toCharArray();
  352.        
  353.         for(int i=0; i<cifri1.length; i++)
  354.         {
  355.             lista1.insertFirst(cifri1[i] - '0');;
  356.            
  357.         }
  358.        
  359.         for(int i=0; i<cifri2.length; i++)
  360.         {
  361.            
  362.             lista2.insertFirst(cifri2[i] - '0');;
  363.         }
  364.        
  365.    
  366.        
  367.         calculate(lista1, lista2);
  368.  
  369.     }
  370.  
  371. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top