Форум программистов, компьютерный форум CyberForum.ru

Почти счастливый билет - C++

Восстановить пароль Регистрация
 
el3shka
0 / 0 / 0
Регистрация: 15.11.2012
Сообщений: 19
02.06.2013, 10:45     Почти счастливый билет #1
В гугле полно задач про "Счастливые билеты", а у меня возникла проблема с "Почти счастливыми билетами.

Вот задача - Назовем “почти счастливым” билетом билет, который можно сделать “счастливым” с помощью некоторой перестановки цифр билета. Например, билет с номером 125783 является “почти счастливым” билетом, так как можно переставить цифры 2 и 7, чтобы получился “счастливый” билет 175283. Билеты, “счастливые” без перестановки цифр (например, 123411), не являются “почти счастливыми”. Подсчитать количество “почти счастливых” билетов среди билетов с шестизначными номерами от 000000 до 999999.

Помогите реализовать сие чудо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2013, 10:45     Почти счастливый билет
Посмотрите здесь:

Счастливый билет C++
Счастливый билет! C++
C++ Счастливый билет
C++ счастливый билет
счастливый билет C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.06.2013, 11:15     Почти счастливый билет #2
el3shka, сколько перестановок можно(нужно) сделать для того, чтобы "почти счастливый" стал "счастливым"?
el3shka
0 / 0 / 0
Регистрация: 15.11.2012
Сообщений: 19
02.06.2013, 11:30  [ТС]     Почти счастливый билет #3
Получается перестановок будет 9, например есть билет 123.456, мы может менять местами число 1 с числами 4,5,6. Также будет с числом 2 и 3.

Добавлено через 9 минут
Нашел в инете исходник один, чуток переделал, получилось так -
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "stdafx.h"
#include <iostream> 
#include <iomanip> 
using namespace std; 
int main() 
{ 
    freopen ("input.txt","r",stdin); 
    freopen ("output.txt","w",stdout); 
    char a,b,c,x,y,z; 
    cin.get(a); 
    cin.get(b); 
    cin.get(c); 
    cin.get(x); 
    cin.get(y); 
    cin.get(z); 
if ((a+b+x) == (c+y+z)) cout << "YES - nearly lucky";
    else
        if ((a+b+y) == (x+c+z)) cout << "YES - nearly lucky";
        else 
            if ((a+b+z) == (x+y+c)) cout << "YES - nearly lucky";
            else
                if ((x+b+c) == (a+y+z)) cout << "YES - nearly lucky"; 
                else
                    if ((y+b+c) == (x+a+z)) cout << "YES - nearly lucky";
                    else
                        if ((z+b+c) == (x+y+a)) cout << "YES - nearly lucky"; 
                        else
                            if ((a+y+c) == (x+b+z)) cout << "YES - nearly lucky"; 
                            else
                                if ((a+x+c) == (b+y+z)) cout << "YES - nearly lucky";
                                else
                                    if ((a+z+c) == (x+y+b)) cout << "YES - nearly lucky"; 
                                    else cout << "NO"; 
}
Но запара в том, что я ввожу номер билета с текстовика, как бы это сделать все, чтобы выводилось в консоли со счетчиком общей суммы "почти счастливых билетов"? Добавить sum++?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.06.2013, 12:14     Почти счастливый билет #4
Родил такой вариант:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <string>
#include <cstdlib>
#include <iomanip>
 
int sum( int value )
{
    int sum = 0;
    while( value )
    {
        sum += value % 10;
        value /= 10;
    }
    return sum;
}
 
bool lucky( int value )
{
    return( sum( value/1000 ) == sum( value%1000) );
}
 
 
int digit( int value, int offset )
{
    for( int i=0; i<offset; ++i )
    {
        value /= 10;
    }
    return value % 10;
}
 
bool almostlucky( int value )
{
    if( lucky( value ) ) return false;
    
    int lsum = sum( value/1000 );
    int rsum = sum( value%1000 );
 
    for( int l=0; l<3; ++l )
    {
        for( int r=0; r<3; ++r )
        {
            int ldigit = digit( value / 1000, l);
            int rdigit = digit( value % 1000, r);
 
            if( lsum - 2*ldigit + 2*rdigit - rsum == 0 )
            {
                return true;
            }
        }
    }
    return false;
}
 
int main()
{
    int cnt = 0;
    for( int i=0; i<999999; ++i )
    {
        if( almostlucky( i ) )
        {
            std::cout <<  std::setfill ('0') << std::setw (6) << i << std::endl;
            cnt++;
        }
    }
 
    std::cout << "Almost lucky count: " << cnt << std::endl;
 
    std::system( "pause" );
}
el3shka
0 / 0 / 0
Регистрация: 15.11.2012
Сообщений: 19
02.06.2013, 12:22  [ТС]     Почти счастливый билет #5
Довольно занятный код.)
А можно немного разобрать его?
Не совсем понял алгоритм.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.06.2013, 15:36     Почти счастливый билет #6
el3shka, sum считает сумму цифр в числе.
lucky выясняет "счастливое" ли число.
digit возвращает заданную цифру числа.
almostlucky - путем перестановки цифр из левой в правую часть числа выясняем станет ли оно "счастливым"
Yandex
Объявления
02.06.2013, 15:36     Почти счастливый билет
Ответ Создать тему
Опции темы

Текущее время: 21:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru