Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 19. 02. 2013 21:31
Permutacie Java
Zdravím, potreboval by som pomocť s algoritmom, ktory mi vypise všetky 5 bitove cisla, v ktorych su 3 bity jednotkove, ostatne nulove.
tzn niečo taketo:
Pocet moznosti pre 5 nad 3 = 10
1. 00111
2. 01011
3. 01101
4. 01110
5. 10011
6. 10101
7. 10110
8. 11001
9. 11010
10. 11100
mne by stačilo, aby som vygeneroval všetky možne 5tice zložene z číslel 0 1 (ostatne zvladnem sam)
00000
00001
00010
00011
00100
.....
zvyšok by som už spravil, ale potrebujem tento generator čísel...(idealne ich uložiť do arraylistu, alebo do 2 rozmerneho pola)
Offline
#2 21. 02. 2013 02:50 — Editoval RePRO (21. 02. 2013 02:57)
- RePRO
- Místo: Jihlava
- Příspěvky: 363
- Škola: AI VŠPJ (09-12, Bc.)
- Pozice: programátor
- Reputace: 11
- Web
Re: Permutacie Java
Zdravím,
v Javě existuje toBinaryString. Můžeme si to naimplementovat následovně:
Code:
String s = "0000000";
for (int i = 0; i < 5; i++) {
System.out.print(s);
System.out.println("\t (" + Integer.valueOf(s, 2) + ")");
s = Integer.toBinaryString(Integer.valueOf(s, 2) + 1);
}Výstup:
0000000 (0)
0000001 (1)
0000010 (2)
0000011 (3)
0000100 (4)
Pomohlo?
Srdcem trochu-programátor, duší rádoby-matematik a povoláním analytik-vývojář.
Offline
#6 26. 02. 2013 02:48
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Permutacie Java
Nevim, jakym to mas zpusobem, tak nevim, o kolik je tohle efektivnejsi - pro to N = 5 a K = 3 to jde treba takhle, ale neni to obecne:
Code:
public static ArrayList<Integer> generate(){
ArrayList<Integer> returnedList = new ArrayList<Integer>();
for (int bit1 = 1<<4; bit1 >= 1<<2; bit1 >>>= 1){
for (int bit2 = bit1 >> 1; bit2 >= 1<<1; bit2 >>>= 1){
for (int bit3 = bit2 >> 1; bit3 >= 1<<0; bit3 >>>= 1){
returnedList.add(bit1 | bit2 | bit3);
}
}
}
return returnedList;
}Take jsem to zkousel obecne, ale neukladat to Integeru, ale do pole booleanu (nevim, jak bys to potreboval, aby se to lehko dalo vypsat, ale pres ty Integery by to asi bezelo rychleji)
Code:
public static ArrayList<boolean[]> generate(int N, int K) {
ArrayList<boolean[]> returnedList = new ArrayList<boolean[]>();
generateBoolean(N, K, returnedList, new boolean[N]);
return returnedList;
}
public static void generateBoolean(int N, int K,
ArrayList<boolean[]> destinationArray, boolean[] generatedMask) {
for (int bit = N; bit >= K; bit--) {
generatedMask[bit - 1] = true;
if (K > 1) {
generateBoolean(bit - 1, K - 1, destinationArray, generatedMask);
} else {
destinationArray.add(generatedMask.clone());
}
generatedMask[bit - 1] = false;
}
}Tenhle druhy pripad by sel lehko predelat na ten Integer, jinak ale kdyztak dej vedet, jestli to pomohlo.
Offline
#7 26. 02. 2013 14:39
Re: Permutacie Java
pred pár dnami som to vyriešil týmto sposobom:
/**
* Program vygeneruje 2 rozmerne pole ktore obsahuje vsetky kombinacie 1 a 0,
* ktore mozu nastav na zadanom pocte bitov. Naslednje ich prevediet do
* 1 rozmerneho pola, a odstrani tie, ktore maju mensi resp. vacsi pocet jednotiek
* ako je zadane parametrom int pocetJednotiek. Nasledne vypise vsetky zostavajuce
* kombinacie.
*
* @version 20.2.2012
*/
public class NewClass {
public static void main(String[] args) {
int pocetCisel = 9;
int pocetJednotiek = 3;
int a = 1;
for (int i = 0; i < pocetCisel; i++) {
a = 2 * a;
}
//generuj vsetky pocetCisel bitove cisla a uloz ich do 2 rozmerneho pola
int k = 0;
String pole[][] = new String[a][pocetCisel];
int pomoc = 2;
int yIndex = 0;
int cnt2 = 0;
while (k < pocetCisel) {
for (int i = yIndex; i < a; i++) {
pole[i][k] = "1";
yIndex++;
cnt2++;
if (cnt2 == a / pomoc) {
break;
}
}
cnt2 = 0;
for (int i = yIndex; i < a; i++) {
pole[i][k] = "0";
yIndex++;
cnt2++;
if (cnt2 == a / pomoc) {
break;
}
}
cnt2 = 0;
if (yIndex == a) {
pomoc = pomoc * 2;
k++;
yIndex = 0;
cnt2 = 0;
}
}
//preved ich z 2 rozmerneho do 1 rozmerneho pola
String pole2[] = new String[a];
String s = "";
for (int i = 0; i < pole.length; i++) {
for (int j = 0; j < pole[0].length; j++) {
s = s + pole[i][j];
}
pole2[i] = s;
s = "";
}
//vymaz z tade tie, ktore maju viac ako pocetJednotie jednotiek
int poom = 0;
for (int j = 0; j < a; j++) {
String ss = pole2[j];
for (int i = 0; i < pocetCisel; i++) {
if (ss.charAt(i) == '1') {
poom++;
}
if (poom > pocetJednotiek) {
pole2[j] = "z";
break;
}
}
poom = 0;
}
//vymat z tade tie, ktore maju viac ako pocetMiest-pocetJednotiek nul
for (int j = 0; j < a; j++) {
String ss = pole2[j];
if (ss != "z") {
for (int i = 0; i < pocetCisel; i++) {
if (ss.charAt(i) == '0') {
poom++;
}
if (poom > pocetCisel - pocetJednotiek) {
pole2[j] = "z";
break;
}
}
poom = 0;
}
}
//vypis tie co zostali
int index = 1;
for (int i = 0; i < a; i++) {
if (pole2[i] != "z") {
System.out.format("%3d. %s\n", index, pole2[i]);
index++;
}
}
}
}
Offline