Le coin des beaux problèmes de programmation

nicolas.patrois · February 2023

gebrane a dit :

Problème 3 ( Programme pour vérifier une conjecture jusqu’à une limite)
Soit la conjecture "Tout entier naturel qui est à la fois un carré et un cube est une puissance de 6."

carrés={n**2 for n in range(31622)}
cubes={n**3 for n in range(1001)}
cubocubes={n**6 for n in range(32)}
print(cubocubes-cubes-carrés)
print(cubocubes<=(cubes|carrés))

Doit afficher set() puis True.

celine_L, ton script crée des générateurs, pas des listes. Tu auras une surprise lors de l’affichage.

dp a dit :

Un problème sympa récupéré sur leetcode : Un entier naturel est dit magique s’il est divisible par $a$ ou $b$. Étant donné trois entiers naturels $n$, $a$ et $b$, trouver le $n$-ième nombre magique.

Pas du tout optimisé :

a,b=3,5
n=20
k=0
c=0
while c!=n:
  k+=1
  if k%a==0 or k%b==0:
    c+=1
print(k)

gebrane · February 2023

Bonjour nicolas.patrois

Dans ton programme, tu laisses à la charge de l'utilisateur de vérifier que les carrés cubes figurent bien tous dans la liste des cobocubes

nicolas.patrois · February 2023

Ben non, c’est fait dans le print.

celine_L · February 2023

Oui je sais @nicolas.patrois , cela permet de gagner en mémoire et rapidité, après on gère l'affichage comme on veut.

Médiat_Suprème · February 2023

@Matricule_63 : Je me suis senti obligé de réécrire mon programme, voilà un exemple avec comme source de probabilités Les Chants de Maldoror de Lautréamont et n= 4 :

marcassion ne bandonnerai jamais, vites chez de contres. n'import avec effort autre, j'ai l'un partientent préservé assis, c'est au mille; et lui qui venir si elle phénomène à rompe et seule fleuve larmes

J'aime bien le "fleuve larmes"

Médiat_Suprème · February 2023

Je ne vais pas poster toutes les trouvailles de mon programme, mais j'aime bien : "Marche remplie de silence, l'apparence ridicule."
Pour être honnête, j'ai rajouté la virgule.

dp · February 2023

Solutions rust (avec pour seule dépendance clap, afin de gérer les paramètres de ligne de commande encore que, on pourrait s'en passer) de tous les problèmes de ce fil

Problème 1

use clap::Parser ;

#[derive(Parser)]
struct CLIArguments {
    #[arg(short)]
    number: u64
}

fn solve(n: u64) -> u64 {
    let mut result: u64 = 0 ;
    for i in 1..n {
        result += i*(n/i) ;
    }
    result
}

fn main() {
    let args = CLIArguments::parse() ;
    println!("Solution: {}", solve(args.number)) ;
}

Problème 2

trait Palindrome {
    fn is_palindrome(self) -> bool ;
}

impl Palindrome for u32 {
    fn is_palindrome(self) -> bool {
        let (mut reversed, mut unreversed) = (0, self) ;

        while unreversed > 0 {
            reversed    = (reversed * 10) + (unreversed % 10) ;
            unreversed /= 10 ;
        }

        self == reversed
    }
}

fn solve() -> Vec<u32> {
    let palinsquares = (1..31622).map(|x:u32| x.pow(2))
                                 .filter(|x| x.is_palindrome())
                                 .collect::<Vec<_>>() ;

    palinsquares
}

fn main() {
    println!("Solution: {:?}", solve()) ;
}

Problème 3

use std::collections::HashSet ;

fn solve() -> HashSet<u32> {
    let squares:      HashSet<u32> = (1..31622).map(|x:u32| x.pow(2)).collect::<Vec<_>>().iter().cloned().collect();
    let cubics:       HashSet<u32> = (1..1001) .map(|x:u32| x.pow(3)).collect::<Vec<_>>().iter().cloned().collect();
    let cubicsquares: HashSet<u32> = (1..32)   .map(|x:u32| x.pow(6)).collect::<Vec<_>>().iter().cloned().collect();

    let square = (&cubicsquares - &cubics).iter().cloned().collect() ;
    let set    = (&square - &squares).iter().cloned().collect() ;

    set
}

fn main() {
    println!("Solution: {:?}", solve()) ;
}

Problème 4

use clap::Parser ;

#[derive(Parser, Default)]
struct CLIArguments {
    #[arg(short)]
    number: u64
}

trait PrimalityTest {
    fn is_prime(self) -> bool ;
}

impl PrimalityTest for u64 {
    fn is_prime(self) -> bool {
        if self == 2 || self == 3 {
            return true ;
        }

        if self % 2 == 0 || self % 3 == 0 {
            return false ;
        }

        for i in (5..).step_by(6).take_while(|i| i*i <= self) {
            if self % i == 0 || self % (i+2) == 0 {
                return false ;
            }
        }

        true
    }
}

fn solve(n: u64) -> bool {
    let primes1mod4 = (2..n).map(|p| p)
                            .filter(|p| p % 4 == 1)
                            .filter(|p| p.is_prime())
                            .collect::<Vec<_>>() ;


    for p in primes1mod4 {
        let (mut sum, prod) = (0, (p-1)*(p-2)/3) ;

        for k in 1..p {
            sum += (k.pow(2))/p;
        }

        if sum != prod {
            println!("{}, {}, {}", p, sum, prod);
            return false;
        }
    }

    true
}

fn main() {
    let args = CLIArguments::parse() ;
    println!("{}", solve(args.number)) ;
}

Problème 5

use clap::Parser ;

#[derive(Parser, Default)]
struct CLIArguments {
    #[arg(short)]
    number: usize,
    #[arg(short)]
    a: u64,
    #[arg(short)]
    b: u64
}

fn solve(n: usize, a: u64, b: u64) -> u64 {
    return (2..).map(|p:u64| p)
                .filter(|p| p % a == 0 || p % b == 0)
                .take(n)
                .last()
                .unwrap();
}

fn main() {
    let args = CLIArguments::parse() ;
    println!("{}", solve(args.number, args.a, args.b)) ;
}

Problème 7

Méthode en $O(n^2)$

use rand::Rng ;

#[derive(Debug,Copy,Clone)]
struct Circle {
    origin: (i32,i32),
    radius: i32
}

impl Circle {
    fn new(origin: (i32,i32), radius: i32) -> Self {
        assert!(radius >= 0) ;
        Self { origin, radius }
    }

    fn intersect_with(self, c: Self) -> bool {
           (self.radius - c.radius)^2 <= (self.origin.0 - c.origin.0)^2 + (self.origin.1 - c.origin.1)^2
        && (self.origin.0 - c.origin.0)^2 + (self.origin.1 - c.origin.1)^2 <= (self.radius + c.radius)^2
    }
}

impl PartialEq for Circle {
    fn eq(&self, other: &Self) -> bool {
        self.origin == other.origin && self.radius == other.radius
    }
}

fn solve(circles: Vec<Circle>) -> Vec<(Circle,Circle)> {
    let mut intersect: Vec<(Circle,Circle)> = vec![] ;

    for circle1 in &circles {
        for circle2 in &circles {
            if circle1 != circle2 {
                if circle1.intersect_with(*circle2) {
                    intersect.push((*circle1,*circle2));
                }
            }
        }
    }

    intersect
}

fn main() {
    let mut rng = rand::thread_rng() ;
    let mut circles: Vec<Circle> = vec![] ;

    for _ in 0..10 {
        let new_origin: (i32, i32) = (rng.gen_range(-10..10), rng.gen_range(-10..10)) ;
        let new_radius: i32 =  rng.gen_range(0..10) ;
        let new_circle: Circle = Circle::new(new_origin, new_radius) ;
        circles.push(new_circle) ;
    }

    let solution = solve(circles) ;
    println!("There is {} intersections: {:?}", solution.len(), solution) ;
}

La suite en edit la prochaine fois.

gebrane · February 2023

Merci dp pour ce partage, je vais reprendre tes programme quand suffisamment de recul sur rust, Tu te rends trés utile dans ce fil et merci pour ce temps consacré aux autres

Le coin des beaux problèmes de programmation

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 20