Форум программистов [Powered by Invision Power Board]

Цитата

Написать программу определения количества шестизначных "счастливых" трамвайных билетов, у которых сумма первых трех цифр совпадает с суммой трех последних.
Оптимизировать решение по времени выполнения. Количество билетов вывести в файл output.txt

Код


package olympicexercises;

import java.io.*;
import java.util.*;
import java.text.*;


public class LuckyNumbersSolver
{

  /**
   * Нахождение шестизначных "счастливых" трамвайных билетов, у которых сумма первых трех цифр совпадает с суммой трех
   * последних
   *
   * @param numbers - массив номеров
   * @return массив счастливых номеров
   */
  private static List<String> findLuckyNumbers(List<String> numbers)
  {
    List<String> luckyNumbers = new ArrayList<String>();
    for (String number : numbers) {
      int sumLeft = Character.digit(number.charAt(0), 10) + Character.digit(number.charAt(1), 10) + Character
          .digit(number.charAt(2), 10); // суммируем первые 3 цифры в номере
      int sumRight = Character.digit(number.charAt(4), 10) + Character.digit(number.charAt(5), 10) + Character
          .digit(number.charAt(6), 10); // суммируем последние 3 цифры в номере
      if (sumLeft == sumRight) { // проверяем на совпадение сумму первых трех цифр с суммой трех последних
        luckyNumbers.add(number); // добавляем "счастливый" номер в массив
      }
    }
    return luckyNumbers;
  }


  public static void main(String[] args) throws IOException
  {
    final List<String> numbers = new ArrayList<String>();
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMinimumIntegerDigits(6);
    final int start = 0, end = 999999;
    final String from = nf.format(start), to = nf.format(end), message;

    for (int i = start; i <= end; i++) // инициализация коллекции номеров для поиска
      numbers.add(nf.format(i));

    System.out.println(findLuckyNumbers(numbers));
    message = "Count of lucky train tickets from " + from + " to " + to + ": " + findLuckyNumbers(numbers).size();
    System.out.println(message);

    // Выгрузим "счастливые" номера в файл
    final PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("src/olympicexercises/output.txt")));
    out.println(message);
    out.println(findLuckyNumbers(numbers));
    out.close();
  }
}

Цитата(dorogoyIV @ 7.10.2010, 18:33

)

начинать можно с билета номер 1001

Цитата(SelenIT @ 7.10.2010, 17:37

)

Как минимум, основной цикл можно сократить в тысячу раз ;)

Цитата(m1st @ 19.10.2010, 11:58

)

Так мы пропускаем билет "000 000".

Код


import java.io.*;
import java.text.*;
import java.util.*;

public class Test
{
 private static Vector <String> v = new Vector <String> ();

 public static void main(String [] args)
 {
  int summLeft = 0;
  long count = 0;
  NumberFormat nf = NumberFormat.getInstance();
  nf.setMinimumIntegerDigits(3);
  long start_time = System.currentTimeMillis();

  for(int i = 1; i < 1000; i++)
  {
   String sLeft = nf.format(i);
   int firstLeft = Character.digit(sLeft.charAt(0), 10);
   int secondLeft = Character.digit(sLeft.charAt(1), 10);
   int thirdLeft = Character.digit(sLeft.charAt(2), 10);

   summLeft = firstLeft + secondLeft + thirdLeft;

   int summRight = 0;

   for(int j = 1; j < 1000; j++)
   {
    String sRight = nf.format(j);
    int firstRight = Character.digit(sRight.charAt(0), 10);
    int secondRight = Character.digit(sRight.charAt(1), 10);
    int thirdRight = Character.digit(sRight.charAt(2), 10);

    summRight = firstRight + secondRight + thirdRight;

    if(summRight == summLeft)
    {
     v.add(sLeft + " " + sRight);
     count++;
    }
   }
  }
  writeVector(v);

  System.out.println("spended time = " +
            (System.currentTimeMillis() - start_time) / 1000 + "." +
            (System.currentTimeMillis() - start_time) % 1000 + " sec");
  System.out.println("count = " + count);
 }

 private static void writeVector(Vector <String> v)
 {
  try
  {
   BufferedWriter bw = new BufferedWriter(
          new FileWriter(new File("C:\\LuckyTickets.txt"), true));

   for(int i = 0; i < v.size(); i++)
   {
    bw.write(v.get(i));
    bw.newLine();
   }
   bw.close();
  }
  catch(Exception ex){}
 }
}

Цитата(Connie @ 8.10.2010, 09:05)

http://window.edu.ru/window/library?p_rid=37295

стр. 43

Код


package olympicexercises;

public class LuckyNumbersSolverV3
{
  final static int limit = 9;

  static Integer CDecomposition(int j, int m, int n)
  {
    if (m == 0) {
      if (n <= limit)
        return 1;
      else
        return 0;
    }
    if (m == n) {
      return 1;
    }
    if (j > 0) {
      return CDecomposition(j - 1, n - 1, m) + CDecomposition(j, n - 1, m - 1);
    }
    else {
      return CDecomposition(limit, n - 1, m - 1);
    }
  }


  static Integer CountLuckyTicket()
  {
    int count = 0;
    int b;
    for (int i = 0; i < 27; i++) {
      b = CDecomposition(limit, i + 2, 2);
      // подсчет числа разложений для i-го класса
      count = count + b * b;
    }
    return count;
  }


  public static void main(String[] args)
  {
    System.out.println(CountLuckyTicket());
  }
}