Προγραμματιστική πρόκληση Νο 1 : Άθροισμα διαιρετέων αριθμών

Γράψτε ένα πρόγραμμα που να υπολογίζει το άθροισμα των αριθμών που διαιρούνται με το 3 και με το 5 μέχρι ένα δεδομένο αριθμό. Οποιαδήποτε γλώσσα

Για να δούμε αν υπάρξει ενδιαφέρον :slight_smile:

3 Likes

μήπως ήθελες να γράψεις ή και όχι και;
Γιατί τώρα εννοείς απλώς τα πολλαπλάσια τού 15.

Αλλά οκ (python)

def souma(n):
    i = 15
    s = 0
    while True:
        if i > n: return s
        
        s += i
        i += 15
2 Likes

Αν είναι ή τελικά η πρόταση, θα είναι κάπως έτσι :

#!/usr/bin/env python
arithmos=int(input("Enter a number: "))
x=0
summ=0
if arithmos<3:
	print(summ)
elif (arithmos>=3)and(arithmos<5):
	summ=3
	print(summ)
elif arithmos==5:
	summ=8
	print(summ)
else:
	summ=8
	for x in range(6,arithmos+1):
		if (x%3==0)or(x%5==0):
			summ+=x
	print(summ)
1 Like

καλό είναι να συνηθίζουμε τον κόσμο με συναρτήσεις

def souma(n):
    s = 0
    i = 3
    while True:
        if i > n: return s
        if i%3 == 0 or i%5 == 0: s += i
        i += 1
2 Likes

Θεωρώ να διαιρούνται με 3 ή 5, μέχρι και το δεδομένο αριθμό, σε C:

    #include <stdio.h>

    int sum_calculate(int user_value) {
    	int i, sum = 0;

    	for(i = 0; i <= user_value; i++) {
    		if((i % 3 == 0) || (i % 5 == 0)) {
    			sum = sum + i;
    		}
    	}

    	return(sum);
    }

    int main(int argc, char *argv[]) {
    	int user_value;

    	printf("Enter a value:");
    	scanf("%d", &user_value);

    	printf("SUM: %d\n", sum_calculate(user_value));

    	return 0;
    }
2 Likes

:+1: επειδή έχεις συνάρτηση για τον υπολογισμό :slight_smile:

Ας δώσω και το «ολοκληρωμένο» πρόγραμμα σε python

#!/bin/python3
#proklisi1.py

def souma(n):
    s = 0
    i = 3
    while True:
        if i > n: return s
        if i%3==0 or i%5==0: s += i
        i += 1

def main(n=None):
    if n is None:
        n = int(input('Δώσε αριθμό: '))
    
    print ("Άθροισμα:", souma(n))

if __name__ == '__main__':
    import sys
    try:
        n = int(sys.argv[1])
        main(n)
    except IndexError:
        main()
    except ValueError:
        print(':P')
2 Likes

Να ευχαριστήσω κατ’ αρχήν τις πρώτες συμμετοχές. Ελπίζω να το βρήκατε ένα ευχάριστο πρόβλημα και να μάθαμε και όσοι πήραν μέρος με κώδικα και όσοι το διαβάζουν κάτι παραπάνω. Σκοπός είναι να ξεσκουριάζουμε, να βλέπουμε κώδικα σε άλλες γλώσσες, και να κάνουμε χαβαλέ, και όχι να κάνουμε κάποιο διαγωνισμό.

Με βάση αυτά μερικές παρατηρήσεις. Σε όσους επέλεξαν την C/C++ γιατί διαλέξατε ως τύπο τον int; Ένας unsigned long long δεν θα ταίριαζε εδώ καλύτερα; (τουλάχιστον σε μια ποιο γενική περίπτωση). Επίσης αν ήθελα να πω ή δεν θα έλεγα και. Το πρόβλημα είναι σαφές. Λέει και, καθώς για δυο συγκεκριμένους αριθμούς που δεν επιλέχθηκαν τυχαία. Αλλιώς για δυο τυχαίους φυσικούς αριθμούς θα ήταν μάλλον μπερδεψοδουλειά :exploding_head: Λύσατε λοιπόν το λάθος πρόβλημα :grin:

Εκτιμώ βέβαια το γεγονός πως πήγατε να λύσετε το δύσκολο πρόβλημα, μιας και το ή μοιάζει δυσκολότερο, αλλά θα διαφωνήσω σε αυτό. Έθεσα το δύσκολο πρόβλημα, όχι το εύκολο. Αν λύσεις το δύσκολο πρόβλημα του και, τότε το πρόβλημα του ή είναι μάλλον προφανές :innocent:

Ξέρουμε βέβαια όλοι μας πως αν τραβήξω την διαγώνια σε ένα παραλληλόγραμμο το τρίγωνο που θα προκύψει θα έχει το μισό εμβαδόν, αλλά το λέω για να μην λέτε πως δεν σας μπέρδ βοήθησα :smile:

Περιμένω τις βελτιωμένες λύσεις σας :slight_smile:

Μα αν φτιάξουμε κλειστό τύπο, τότε γιατί να χρησιμοποιήσουμε υπολογιστή; :stuck_out_tongue:

1 Like

Για τον ίδιο λόγο που η δεσμευμένη λέξη constexpr υπάρχει στην C++ :grin:

Σε ένα βιβλίο προγραμματισμού, πάντως δίνει μια λύση σε αλγοριθμικό \mathbf{O}(n) πάνω κάτω σαν αυτή που δώσατε.

Κρίμα γιατί το πρόβλημα είναι πολύ βαθύ. Αν έχεις μια συνάρτηση \sum(x_1,max) μπορείς να υπολογίσεις με αυτή το \sum(x_1\,\text{or}\, x_2, max ); Και πιάνουμε ήδη πολύ επικίνδυνα μονοπάτια :slight_smile:

Έχω συνηθίσει να χρησιμοποιώ τους απλούς τύπους πρώτα και να τους αλλάζω μόνο αν προκαλούν πρόβλημα και επειδή δεν διευκρινίζεται μέγιστη τιμή του δεδομένου αριθμού δεν το έδωσα σημασία. Αλλά όντως το unsigned long long ταιριάζει καλύτερα.

Περιμένω να δω και άλλες γλώσσες, είμαι σίγουρος ότι η κοινότητα καλύπτει μεγάλο εύρος. :slightly_smiling_face:

2 Likes

Επειδή το βρήκα :grinning:, δεν θα το ποστάρω ακόμα, αλλά θα δώσω λίγο χρόνο και στους υπόλοιπους, όσο διαμορφώνω ένα πλήρως λειτουργικό πρόγραμμα τερματικού που θα κάνει αυτή τη δουλιά για σετ διαρετών που θα δίνεται από τον χρήστη, και θα έχει και μενού βοήθειας. Το παρών θα το κάνω φυσικά και ως ένα αποτέλεσμα της συνολικής εμπειρίας και όλων των προηγουμένων απαντήσεων.

1 Like

Εγώ πάλι λέω να το σποϊλάρω…
Ας πάρουμε κάτι λίγο πιο γενικό από το 3 και 5, που είναι πρώτοι, οπότε ουσιαστικά το πρόβλημα ανάγεται στο ‘διαιρείται με το 15’…
Semi-efficient:
Οι παραπάνω λύσεις, με τη διαφορά ότι μπορείς αρχικά να κανεις increment κατά 15, ξεκινώντας από το ΕΚΠ των 2 αριθμών (δηλαδή 15), καθώς οτιδήποτε ενός του (Ν,Ν+15) συνόλου, όπου Ν ένας διαιρούμενος με το 15 αριμός, προφανώς δεν είναι διαιρέτης του. Still, Ο(n) complexity.
Efficient:
Ουσιαστικά αυτό που είπε ο Τάλος γεωμετρικά, γραμμένο αλγεβρικά. Με δεδομένα “a”, “b” τους δύο ακεραίους και με δεδομένο μέγιστο το “Μ”

  • Βρίσκουμε το ΕΚΠ των δύο αριθμών – O(logn) complexity
    lcm = calculate_lcm(a,b) //παραλείπω το implementation λόγω google
  • Βρίσκουμε το μεγαλύτερο αριθμό που διαιρείται με το ΕΚΠ – Ο(1) complexity
    max_divisible = (Μ % lcm == 0) ? M : (M - M % lcm)
  • Αν λάβουμε υπόψη την προφανή και ταυτόχρονα όχι και τόσο προφανή βελτιστοποίηση του “semi-efficient” αλγορίθμου, ουσιαστικά η λύση είναι το κάτωθι άθροισμα
    lcm + 2 * lcm + 3 * lcm … + max_divisible = lcm * (1 + 2 + 3 + … + max_divisible/lcm)
  • Καταλήξαμε λοιπόν σε μία ωραιότατη αριμητική πρόοδο, η οποία λύνεται σε O(1), απλά χρησιμοποιώντας την παρακάτω σχέση
    sum = ( count / 2 ) * ( lcm + max_divisible)
  • Το να βρούμε το “count” είναι επίσης εύκολο και ομοίως λύνεται σε Ο(1) complexity
    count = ( ( max_divisible - lcm ) / lcm ) + 1
  • Συνολικά σε μία γραμμή:
    sum = ( ( ( max_divisible - lcm ) / lcm + 1 ) / 2 ) * ( lcm + max_divisible ) =>
    sum = max_divisible/2 + max_divisible^2 /2*lcm

Συνολικό time complexity: Ο(logn) -> Oυσιαστικά ή εύρεση του ΕΚΠ…

ΥΓ: Το γράψιμο σε real code το αφήνω σε εσάς, κυρίως λόγω βαρεμάρας…
Cheers

3 Likes

Θα δώσω και εγώ μια δική μου λύση που δεν δουλεύει πάντα, αλλά είναι καθαρό \mathcal{O}(1). Υπάρχει πλέον όλη η πληροφορία για όποιον θέλει να ενώσει τα κομμάτια, ή τουλάχιστον έτσι ελπίζω λολ

#include <cassert>

using Nat = unsigned long long;
int main() {
  constexpr auto fSum = [](auto div1, auto div2, auto max) {
    constexpr auto pSum = [](auto div, auto max) {
      auto m = max / div;
      return m * (m + 1) / 2 * div;
    };
    return pSum(div1, max) + pSum(div2, max) - pSum(div1 * div2, max);
  };
  assert(fSum(3, 5, 100) == naive_sum(3, 5, 100));
//  assert(fSum(3*5, 5, 100) == naive_sum(3*5, 5, 100));

  return EXIT_SUCCESS;
}

%CE%B5%CE%B9%CE%BA%CF%8C%CE%BD%CE%B1

Αν έχουμε 3 διαιρέτες;

1 Like

Και το συνολικό προγραμματάκι που σας οφείλω από πριν. Υλοποίηση στην αγαπημένη C++. (Ένα χρόνο είχα να την πιάσω στα χέρια μου την κούκλα με την σχολή που έμπλεξα και τα πάντα είναι java)

Για τον πλήρη κώδικα σε ανθρώπινη μορφή και το εκτελέσιμο καθώς και την εικόνα, μπορείτε να τα βρείτε στο Google drive μου. https://drive.google.com/open?id=1WdALYdz-BexNC7m3Q7dPH8RzJmccLHBy

Πηγαίoς Κώδικας
//TDSC v1.0
//Date:13-08-2019
//Author:orfibous
//Special Thanks for their contribution to linux-user.gr members:
//@lucinos
//@kapgeorge
//@Maras
//@gmotux
//@Talos
//Compilation instractions:
//Open a terminal and move to the folder containing TDSC.cpp (this file)
//Use: g++ -o TDSC TDSC.cpp 
//Use: ./TDSC --help To learn how to use the application
//TODO implement vectors to dynamicly get arguments and allow N number of divisors. One suggestion would be to also add a new argument to indicate the N number of divisors the user wants.

#include <iostream>
#include <cstring>
#include <chrono>
#include <math.h>
using namespace std;
int debugmode=0;

void sumCalculateInefficient(unsigned long long userValues[3]){
    auto start = chrono::steady_clock::now();
    unsigned long long  sum = 0;
    for(unsigned long long  i = 0; i <= userValues[0]; ++i) {
            if((i % userValues[1] == 0) && (i % userValues[2] == 0)) {   		
            	sum+= i;
    		}           
    }
    cout << "Inefficient algorithm "<<"SUM: "<< sum << "\n";
    auto end = chrono::steady_clock::now();
    auto diff = end - start;
    cout << chrono::duration <double, nano> (diff).count() << " ns" << endl;
    return ;
}

void sumCalculateSemiEfficient(unsigned long long userValues[3]){
    auto start = chrono::steady_clock::now();
    unsigned long long  sum = 0;
    unsigned long long  step =  userValues[1] * userValues[2];
    for(unsigned long long  i = 0; i <= userValues[0]; i+= step) {               
        sum+= i;
    }
    cout << "Semi-Efficient algorithm "<< "SUM: "<< sum << "\n";
    auto end = chrono::steady_clock::now();
    auto diff = end - start;
    cout << chrono::duration <double, nano> (diff).count() << " ns" << endl;
    return ;
}

unsigned long long gcd(unsigned long long int a, unsigned long long int b){        
    if(b==0)
        return a;
    return gcd(b,a%b);
}

unsigned long long lcm(unsigned long long a,unsigned long long b){     
    if(a>b)
        return (a/gcd(a,b))*b;
    else
        return (b/gcd(a,b))*a;    
} 

void sumCalculateEfficient(unsigned long long  userValues[3]){   
    auto start = chrono::steady_clock::now();   
    unsigned long long  sum = 0;
    unsigned long long lcmValue = lcm(userValues[1],userValues[2]);   
    unsigned long long max_divisible = (userValues[0] % lcmValue == 0) ? userValues[0] : (userValues[0] - userValues[0] % lcmValue);
    sum = ( ( ( max_divisible - lcmValue ) / lcmValue + 1 ) / 2 ) * ( lcmValue + max_divisible );
    cout << "Efficient algorithm "<< "SUM: "<< sum << "\n";
    auto end = chrono::steady_clock::now();
    auto diff = end - start;   
    cout << chrono::duration <double, nano> (diff).count() << " ns" << endl;
    return ;
}

void printInfo(){    
    cout <<"TDSC v1.0 (Two divisors Sum Calculator) was created as a fun summer excersice introduced by @Talos in linux-user.gr (12-08-2019).\nThe excersise was about making an algorithm that would calculate the sum of numbers divided by both 3 and 5 until a given number. \nTDSC solution is a result of all the previous answers to the problem.\nSpecial Thanks for their contribution to linux-user.gr members:\n@lucinos\n@kapgeorge\n@Maras\n@gmotux\nAuthor:@orfibous\n";
    return ;
}

void printHelp(){
    cout <<"Usage: ./TDSC [OPTION]... [maxNumber] [divisor_A] [divisor_B]\n";
    cout <<"TDSC takes two numbers as divisors A,B and calculates the sum of all numbers from {0,MaxNumber} that are divided perfectly by both A and B. The application uses 3 different methos to calculate the sum and calculates the time it takes to execute each of them.\n";
    cout <<"\nOptions list:\n    -i, --info            display information about this application\n    -d, --debug           display debug information to terminal\n    -h, --help            display this help and exit\n";
    return ; 
}

int inputControl(unsigned long long  userValues[3], int argc, char *argv[]){
    if(argc <= 1) cout <<"Error:No arguments please read Help (Use: ./TDSC --help)";   
    for(unsigned long long  i= 1;i<argc-2;++i){
        if(strcmp(argv[i],"-i") ==0 || strcmp(argv[i],"--info") ==0){
            printInfo();
            return 1; 
        }
        if(strcmp(argv[i],"-d") ==0 || strcmp(argv[i],"--debug") ==0){
           debugmode = 1;            
        }
        if(strcmp(argv[i],"-h") ==0 || strcmp(argv[i],"--help") ==0){
            printHelp();
            return 1; 
        }    
    }
    userValues[0] = strtoull(argv[argc-3],nullptr,0);
    userValues[1] = strtoull(argv[argc-2],nullptr,0);
    userValues[2] = strtoull(argv[argc-1],nullptr,0);
    return 0;
}

int main(int argc, char *argv[]) {
    unsigned long long userValues[3]; 
    if (inputControl(userValues, argc, argv)) return 1;    
    sumCalculateInefficient(userValues);
    sumCalculateSemiEfficient(userValues);
    sumCalculateEfficient(userValues);
return 0;
}

Υ.Γ. Για κάποιον λόγο δεν φαίνονται τα includes στα μπλοκ κώδικα
Υ.Γ.2 Αν κάποιος θέλει όντως μπορεί να βάλει vectors και Loops στους υπολογισμούς ώστε να κάνει το πρόγραμμα να τρέχει για Ν διαιρέτες θα ήταν πολυ ενδιαφέρον.

2 Likes

Γενικευμενο για οποιουσδηποτε 2 αριθμους με οριο σε java:

    package linuxforum;
    import java.util.Scanner;
    /**
     * @author Petros Andrianos
    */
    public class LinuxForum {
        public static void calculatorSum2 ( int a, int b, int number) {
            int step, calcSum;
            calcSum = 0;
            System.out.println("_______________________________");
            System.out.println("Οι αριθμοι εναι :");
            step = a * b;
            for ( int i=step; i<=number; i=i+step ) {
                /*  Ειναι γρηγοροτερη η επιλυση του (a*b ==0) απo το (a == 0) && (b == 0)  */
                if ( ( i % a ) * ( i % b ) == 0 )  {
                    System.out.print(i + ", ");
                    calcSum = calcSum + i;   
                }
            }
            System.out.println("");
            System.out.println("_______________________________");
            System.out.println("Το αθροισμα ειναι: " + calcSum);
        } 
        static void start() {
            Scanner keyboard = new Scanner(System.in);
            int a, b, sum, number;
            System.out.print("Δώσε τον 1ο αριθμό: "); 
            a = keyboard.nextInt();
            System.out.println("");
            System.out.print("Δώσε τον 2ο αριθμό: "); 
            b = keyboard.nextInt();
            System.out.println("");
            System.out.print("Δώσε τον αριθμό οπου θα υπολογισω το αθροισμα\n των αριθμων που διαιρουνται με το " + a + " και το " + b + ": "); 
            number = keyboard.nextInt();
            calculatorSum2(a, b, number);
        } 
        public static void main(String[] args) {
            start();
        }
    }
1 Like

Κάποιος παραπονέθηκε πως περίμενε πολύ περισσότερες γλώσσες υλοποίησης. Θα τον απογοητεύσω δίνοντας μια λύση σε C++, αλλά σε μοντέρνα C++ και όχι σαν την C++ του παππού σου :grin:

constexpr auto orSum = [](std::pair<auto, auto> divs, auto max) {
    auto div1 = divs.first;
    auto div2 = divs.second;

    constexpr auto kSum = [](auto div, auto max) {
        auto m = max / div;
        return m * (m + 1) / 2 * div;
    };

    auto gcd = std::gcd(div1, div2);
    max = max / gcd, div1 = div1 / gcd, div2 = div2 / gcd;
    auto s = kSum(div1, max) + kSum(div2, max) - kSum(div1 * div2, max);

    return s * gcd;
};

Δεν μοιάζει σαν μια καινούργια γλώσσα; Έκανα προσπάθεια να κάνω το πρόγραμμα γενικό. Κάτι που στην Python το έχεις χωρίς καμία απολύτως προσπάθεια. Αλλά, ΑΝ, το ζητούμενο του προγράμματος ήταν να τυπώσει απλά το orSum({3,5},100), τότε ο παραπάνω κώδικας καταρρέει σε ένα απλό print 2418 που είναι η απάντηση, και δεν θα γίνει κανένας απολύτως υπολογισμός όταν τρέχεις το πρόγραμμα. Beat me on it :stuck_out_tongue:

Παραθέτω μόνο την συνάρτηση υπολογισμού, χωρίς κάποια static assert και χωρίς σχόλια. Ο πλήρης κώδικάς. μαζί με κάποια σχόλια για την υλοποιηση, μπορεί να βρεθεί εδώ. Χρησιμοποιεί κάποια καινούργια χαρακτηριστικά, και ίσως έχει νόημα να προσπαθήσεις να τον γράψεις σε ποιο κλασσική γλώσσα ή σε templates για εξάσκηση. Αν υπάρχουν προβλήματα στην κατανόηση του αλγόριθμου, εδώ είμαστε :slight_smile: Για να γίνει compile

 g++ -std=gnu++1z  main.cpp

Python :stuck_out_tongue:

print([i for i in range(int(input("Insert number: "))) if i%3==0 and i%5==0])
4 Likes

και έλεγα δεν θα βρεθείς κάποιος να το σκεφτεί αυτό :slight_smile:

2 Likes

Καλώς ήρθες @gespyrop στην παρέα μας :hugs:

1 Like

Καλώς σας βρήκα! :smiley: