VPF::Задача: Трамвайные билеты. Покритикуйте

m1st

Дата 7.10.2010, 17:27 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 1.11.2006

Репутация: нет
Всего: нет

Цитата

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

Привет, решение данной задачи на Java. Покритикуйте.

Код


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();
  }
}

SelenIT

Дата 7.10.2010, 17:37 (ссылка)

(нет голосов)

Загрузка ...

баг форума

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: нет
Всего: 401

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

--------------------

Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!

dorogoyIV

Дата 7.10.2010, 18:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46

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

Connie

Дата 8.10.2010, 09:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 382
Регистрация: 12.8.2008

Репутация: 1
Всего: 9

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

стр. 43

http://forum.vingrad.ru/forum/topic-139132.html#

Это сообщение отредактировал(а) Connie - 8.10.2010, 09:11

danilka

Дата 8.10.2010, 14:07 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 15.1.2010

Репутация: нет
Всего: нет

И findLuckyNumbers() нужно дернуть один раз.

EgorTheBlade

Дата 17.10.2010, 14:18 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 141
Регистрация: 5.12.2009

Репутация: нет
Всего: -1

А разбить массив на два(первые 3 ,вторые 3) и сравнить их суммы нельзя?

Connie

Дата 17.10.2010, 14:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 382
Регистрация: 12.8.2008

Репутация: 1
Всего: 9

А я вообще думаю, что быстрее не делать выборку, а генерировать и просто проверять вхождение в диапазон.

m1st

Дата 19.10.2010, 11:58 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 1.11.2006

Репутация: нет
Всего: нет

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

)

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

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

Добавлено через 2 минуты и 29 секунд

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

)

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

Расскажите на примере из явы, как? ж)

dorogoyIV

Дата 19.10.2010, 12:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46

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

)

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

такого не бывает - они не программисты, у них счет начинается с 1 smile

dorogoyIV

Дата 19.10.2010, 20:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1503
Регистрация: 26.3.2007

Репутация: 3
Всего: 46

так быстрее

Код


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){}
 }
}

spended time = 1.735 sec
count = 55251

Это сообщение отредактировал(а) dorogoyIV - 19.10.2010, 20:25

m1st

Дата 4.11.2010, 17:54 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 1.11.2006

Репутация: нет
Всего: нет

Цитата(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());
  }
}

Выдаёт:
Exception in thread "main" java.lang.StackOverflowError
at olympicexercises.LuckyNumbersSolverV3.CDecomposition(LuckyNumbersSolverV3.java:19)
...

Что не так?

Это сообщение отредактировал(а) m1st - 5.11.2010, 12:58

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »